`
暴风雪
  • 浏览: 387991 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[网络流]hdoj 3251:Being a Hero

阅读更多

大致题意:
    给出一个由n个点,m条边组成的有向图,给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开,同时你会得到相应的收益值。求总收益的最大值。

 

大致思路:

    网络流经典构图……

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int nMax=2000;
const int mMax=300000;
const int inf=1<<30;
class node{
    public:
    int u,v,next;
    int c;
    int cnm,id;
};node edge[mMax];
int ne, head[nMax];
int cur[nMax], ps[nMax], dep[nMax],n,m,ans,cnts,cntt;
bool f[nMax],ff[nMax];
void addedge(int u, int v,int c,int id){    // dinic的加边,还是有点不同的。
    edge[ne].u = u;
    edge[ne].v = v;
    edge[ne].c = c;
    edge[ne].next = head[u];
    edge[ne].cnm=ne+1;
    edge[ne].id=id;
    head[u] = ne ++;
    edge[ne].u = v;
    edge[ne].v = u;
    edge[ne].c =0;
    edge[ne].next = head[v];
    edge[ne].cnm=ne-1;
    edge[ne].id=id;
    head[v] = ne ++;
}

int dinic(int s, int t){     // dinic模板:源点为s,汇点为t
    int tr, res = 0;
    int i, j, k, f, r, top;
    while(1){
        memset(dep, -1, sizeof(dep));
        for(f = dep[ps[0]=s] = 0, r = 1; f != r;)
            for(i = ps[f ++], j = head[i]; j; j = edge[j].next)
                if(edge[j].c && dep[k=edge[j].v] == -1){
                    dep[k] = dep[i] + 1;
                    ps[r ++] = k;
                    if(k == t){
                        f = r; break;
                    }
                }
        if(dep[t] == -1) break;
        memcpy(cur, head, sizeof(cur));
        i = s, top = 0;
        while(1){
            if(i == t){
                for(tr = inf, k = 0; k < top; k ++)
                    if(edge[ps[k]].c < tr)
                        tr = edge[ps[f=k]].c;
                for(k = 0; k < top; k ++){
                    edge[ps[k]].c -= tr;
                    edge[ps[k]^1].c += tr;
                }
                i = edge[ps[top=f]].u;
                res += tr;          //
            }
            for(j = cur[i]; cur[i]; j = cur[i] = edge[cur[i]].next)
                if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break;
            if(cur[i]){
                ps[top ++] = cur[i];
                i = edge[cur[i]].v;   //
            }else{
                if(top == 0) break;
                dep[i] = -1;
                i = edge[ps[-- top]].u;
            }
        }
    }
    return res;
}
void dfs1(int v){
 //   cout<<"v1 "<<v<<endl;
    f[v] = 1;
  //  cnts++;
    for(int i = head[v]; i != 0; i = edge[i].next){
        int vs=edge[i].v;
        if(f[vs]==0&&edge[i].c)
            dfs1(vs);
    }
}
void dfs2(int v){
  //  cout<<"v2 "<<v<<endl;
    ff[v] = 1;
 //   cntt++;
    for(int i = head[v]; i != 0; i =edge[i].next){
        int vs=edge[i].v;
        if(ff[vs]==0&&edge[edge[i].cnm].c)
            dfs2(vs);
    }
}

int aaa[mMax];
int main(){
    int i,cas,a,b,c,maxflow,fuck,s,t,ans,tim=0;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d%d",&n,&m,&fuck);
        s=1,t=n+1;
        ne=2;
        memset(head,0,sizeof(head));
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c,i);
        }
        ans=0;
        for(i=1;i<=fuck;i++){
            scanf("%d%d",&a,&b);
            addedge(a,t,b,inf);
            ans+=b;
        }
        maxflow=dinic(s,t);
        ans-=maxflow;
        printf("Case %d: %d\n",++tim,ans);
        memset(f,0,sizeof(f));
        memset(ff,0,sizeof(ff));
        dfs1(s);
        dfs2(t);
        int cnt=0;
        for(i=2;i<ne;i+=2){
            if(f[edge[i].u]&&ff[edge[i].v]&&!edge[i].c){
                if(edge[i].id==inf)continue;
                aaa[cnt]=edge[i].id;
           //     cout<<edge[i].id<<"dwadaw"<<endl;
                cnt++;
            }
        }
        cout<<cnt;
        for(i=0;i<cnt;i++){
            cout<<" "<<aaa[i];
        }cout<<endl;
    }
    return 0;
}
 
0
0
分享到:
评论

相关推荐

    HDOJ题目分类 HDOJ题目分类

    5. **应用领域**:字符串处理、网络流、模拟、游戏理论等。 【压缩包子文件的文件名称列表】:HDOJ题目分类.pdf 这个PDF文档很可能包含了HDOJ平台上所有题目的详细分类列表,每种分类下可能有对应的题目编号、题目...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    HDOJ离线版

    HDOJ离线版是该平台的一种特殊形式,它允许用户在没有网络连接的情况下访问和练习HDOJ中的编程题目,对于那些网络环境不稳定或者希望离线学习的程序员来说,这是一个极其宝贵的资源。 离线版通常包含HDOJ平台上的...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ部分简单题(JAVA)

    HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...

    HDOJ1002

    ACM ICPC HDOJ1002

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    hdoj1005 Number Sequence 代码

    ### hdoj1005 Number Sequence 代码分析与解析 #### 一、问题背景与题目概述 在深入了解代码之前,我们先来了解下题目背景。`hdoj1005 Number Sequence` 是杭州电子科技大学在线评测系统(Online Judge,简称OJ)...

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ1003

    ACM ICPC HDOJ1003

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    hdoj:杭电OJ题目源码记录 —— a source code of hdoj acm problem archive

    杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md 是工具自动生成 (无聊...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    ACM HDOJ 课件

    【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...

    hdoj解题代码

    9. 1041.cpp: 可能是一个涉及图论或网络流的问题,需要用到 Ford-Fulkerson 或 Dinic's Algorithm 等算法。 10. 1015.cpp: 最后一个文件可能包含了一个基础的算法问题,比如查找、排序或简单的数学问题,也可能涉及...

Global site tag (gtag.js) - Google Analytics