POJ 2987 Firing 最大流网络流 dinic 模板

https://www.cnblogs.com/137shoebills/p/9100790.html

http://poj.org/problem?id=2987

之前写过这道题，码一个dinic的最大流板子。

经典问题，选了一个点就有些点必须选，输出使选出的点的权值和最大的最少点数，并输出该权值和。

建图就是s向权值为正的点连流量为val的边，权值为负的点向t连流量为-val的边，所有的权值和-最大流就是答案。

类似于https://www.cnblogs.com/137shoebills/p/7786985.html

细节是注意流量会爆int

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<queue>
 7 using namespace std;
 8 #define LL long long
 9 const int maxn=5010;
10 const LL minf=(LL)1e11;
11 int n,m,s,t;
12 LL val[maxn]={};
13 struct nod{
14     int y,next;LL v; 
15 }e[140010];
16 int head[maxn]={},tot=1,dep[maxn]={};
17 queue<int>q;
18 bool vis[maxn]={}; int cnt=0;
19 void init(int x,int y,LL v){
20     e[++tot].y=y;e[tot].v=v;e[tot].next=head[x];head[x]=tot;
21 }
22 int bfs(){
23     q.push(s);
24     memset(dep,0,sizeof(dep));
25     dep[s]=1;
26     while(!q.empty()){
27         int x=q.front();q.pop();
28         for(int i=head[x];i;i=e[i].next){
29             if(e[i].v&&(!dep[e[i].y])){
30                 dep[e[i].y]=dep[x]+1;
31                 q.push(e[i].y);
32             }
33         }
34     }
35     return dep[t];
36 }
37 LL dfs(int x,LL fc){
38     if(x==t)return fc;
39     LL tsn=0;
40     for(int i=head[x];i;i=e[i].next){
41         if(e[i].v&&dep[e[i].y]==dep[x]+1){
42             LL z=dfs(e[i].y,min(fc-tsn,e[i].v));
43             tsn+=z;e[i].v-=z;e[i^1].v+=z;
44             if(tsn==fc)break;
45         }
46     }
47     return tsn;
48 } 
49 LL dinic(){
50     LL tsn=0;
51     while(bfs())tsn+=dfs(s,minf);
52     return tsn;
53 }
54 void getit(int x){
55     if(x==t)return;
56     if(x!=s)++cnt;
57     vis[x]=1;
58     for(int i=head[x];i;i=e[i].next){
59         if(e[i].v&&!vis[e[i].y]){
60             getit(e[i].y);
61         }
62     }
63 }
64 int main(){
65     scanf("%d%d",&n,&m);
66     s=n+1;t=s+1;
67     LL ans=0;
68     for(int i=1;i<=n;++i){
69         scanf("%lld",&val[i]);
70         if(val[i]>=0){init(s,i,val[i]); init(i,s,0); ans+=val[i];}
71         else{init(i,t,-val[i]);init(t,i,0);}
72     }
73     for(int i=1;i<=m;++i){
74         int x,y;
75         scanf("%d%d",&x,&y);
76         init(x,y,minf);init(y,x,0);
77     }
78     ans-=dinic();
79     getit(s);
80     printf("%d ",cnt);
81     printf("%lld
",ans);
82     return 0;
83 }

View Code

POJ 2987 Firing 最大流 网络流 dinic 模板

POJ 2987 Firing 最大流网络流 dinic 模板