[网络流]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;}?