【习题整理】网络流

说明：S,表示超级原点，T表示超级汇点，<i,j,k(,l)>表示i到j建边，流量为k(，费用为l)，某些题由于没有及时纠正码风，板子的常数较大。。。。。

bzoj4177 Mike的农场

题解：考虑割，养牛的收益为a[i],养羊b[i],对于每个位置<S,i,ai> <i,T,bi>分别表示养牛和养羊，对于两个互相影响的位置<i,j,ci>；做最小割可以满足前两个限制；第三个限制，如果全养牛可以获得d，新建一个点x，考虑要求全养牛的位置为集合为s，<S,x,d> , <x,si,inf> , 当si中有一个没有被割，那么<S,x,d>一定被割，养羊同理对T建，设最小割为C,ans = $( sum (a[i]+b[i]) + sum c[i] ) – C $

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 const int N=10010,M=80010;
 5 int S,T,n,m,k,o,hd[N],cur[N],vis[N],d[N];
 6 struct Edge{int v,nt,c,f;}E[M<<1];
 7 char gc(){
 8     static char*p1,*p2,s[1000000];
 9     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
10     return(p1==p2)?EOF:*p1++; 
11 }
12 int rd(){
13     int x=0; char c=gc();
14     while(c<'0'||c>'9')c=gc();
15     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
16     return x;
17 }
18 void adde(int u,int v,int c){
19     E[o]=(Edge){v,hd[u],c,0};hd[u]=o++;
20     E[o]=(Edge){u,hd[v],0,0};hd[v]=o++;
21 }
22 queue<int>q;
23 bool bfs(){
24     for(int i=S;i<=T;i++)vis[i]=d[i]=0;
25     vis[S]=d[S]=1;q.push(S);
26     while(!q.empty()){
27         int u=q.front();q.pop();
28         for(int i=hd[u],v;~i;i=E[i].nt)if(E[i].c>E[i].f){
29             if(!vis[v=E[i].v])vis[v]=1,d[v]=d[u]+1,q.push(v);
30         }
31     }
32     return vis[T];
33 }
34 int dfs(int u,int F){
35     if(u==T||!F)return F;
36     int flow=0,f;
37     for(int i=cur[u];~i;i=E[i].nt){
38         int v=E[cur[u]=i].v;
39         if(d[v]==d[u]+1&&(f=dfs(v,min(E[i].c-E[i].f,F)))){
40             flow+=f,F-=f;
41             E[i].f+=f,E[i^1].f-=f;
42             if(!F)break;
43         }
44     }
45     return flow;
46 }
47 int dinic(){
48     int flow=0;
49     while(bfs()){for(int i=S;i<=T;i++)cur[i]=hd[i];flow+=dfs(S,inf);}
50     return flow;
51 }
52 int main(){
53     freopen("bzoj4177.in","r",stdin);
54     freopen("bzoj4177.out","w",stdout);
55     n=rd();m=rd();k=rd();
56     S=0,T=n+k+1;
57     for(int i=S;i<=T;i++)hd[i]=-1;
58     int ans=0;
59     for(int i=1,x;i<=n;i++){adde(S,i,x=rd());ans+=x;}
60     for(int i=1,x;i<=n;i++){adde(i,T,x=rd());ans+=x;}
61     for(int i=1,x,y,z;i<=m;i++){
62         x=rd();y=rd();z=rd();
63         adde(x,y,z);
64         adde(y,x,z);
65     }
66     for(int i=1,t,a,b;i<=k;i++){
67         t=rd();a=rd();b=rd();
68         ans+=b;
69         if(!a){
70             adde(S,i+n,b);
71             for(int j=1;j<=t;j++)adde(i+n,rd(),inf);
72         }else{
73             adde(i+n,T,b);
74             for(int j=1;j<=t;j++)adde(rd(),i+n,inf);
75         }
76     }
77     ans -= dinic();
78     printf("%d
",ans);
79     return 0;
80 }
81 
82 
83 
84 
85 
86 
87 
88 
89 
90 //一个很好的割；
91 //每个点(S,i,a[i])  (i,T,b[i]); 
92 //相同时代价 (x,y,b)
93 //集合的贡献：新建n+i号节点表示：a==0 , (S,n+i,b) (n+i,si,inf) ; a==1 (si,n+i,inf) (n+i,T,b);
94 //用总的正值减去最小割即可；
95 //注意第三步；
96 //20181210
97

View Code

bzoj3504 [cqoi2014]危桥

题解：a1->a2 an次，b1->b2 bn次，边有通过次数的限制；直接跑最大流判断会有问题，因为可能会有a1->b2 , b1->a2的路径充当流量，交换a1,a2再反向跑一边即可；

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 const int N=55,M=2510;
 5 int S,T,n,o,a1,a2,an,b1,b2,bn,hd[N],vis[N],cur[N],d[N],in[N],out[N],tot;
 6 struct Edge{int v,nt,c,f;}E[M<<1];
 7 void adde(int u,int v,int c){
 8     E[o]=(Edge){v,hd[u],c,0};hd[u]=o++;
 9     E[o]=(Edge){u,hd[v],0,0};hd[v]=o++;
10 }
11 queue<int>q;
12 bool bfs(){
13     for(int i=S;i<=T;i++)vis[i]=d[i]=0;
14     vis[S]=d[S]=1;q.push(S); 
15     while(!q.empty()){
16         int u=q.front();q.pop();
17         for(int i=hd[u],v;~i;i=E[i].nt)if(E[i].c>E[i].f){
18             if(!vis[v=E[i].v])vis[v]=1,d[v]=d[u]+1,q.push(v);
19         }
20     }
21     return vis[T];
22 }
23 int dfs(int u,int F){
24     if(!F||u==T)return F;
25     int flow=0,f;
26     for(int i=cur[u];~i;i=E[i].nt){
27         int v=E[cur[u]=i].v;
28         if(d[v]==d[u]+1&&(f=dfs(v,min(F,E[i].c-E[i].f)))){
29             flow+=f,F-=f;
30             E[i].f+=f,E[i^1].f-=f;
31             if(!F)break;
32         }
33     }
34     return flow;
35 }
36 int dinic(){
37     int flow=0;
38     while(bfs()){for(int i=S;i<=T;i++)cur[i]=hd[i];flow+=dfs(S,inf);}
39     return flow;
40 }
41 int main(){
42     freopen("bzoj3504.in","r",stdin);
43     freopen("bzoj3504.out","w",stdout);
44     while(~scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)){
45         a1++,a2++,b1++,b2++;
46         o=0;S=0;T=n+1;
47         for(int i=S;i<=T;i++)hd[i]=-1;
48         for(int i=1;i<=n;i++){
49             char ch[51];scanf("%s",ch+1);    
50             for(int j=1;j<=n;j++){
51                 if(ch[j]=='O')adde(i,j,1);
52                 else if(ch[j]=='N')adde(i,j,inf);
53             } 
54         }
55         adde(S,a1,an);adde(a2,T,an);
56         int pre1=hd[S],pre2=hd[T],pre3=hd[b1],pre4=hd[b2]; 
57         adde(S,b1,bn);adde(b2,T,bn);
58         if(dinic()!=an+bn){puts("No");continue;}
59         o-=4;for(int i=0;i<o;i++)E[i].f=0;
60         hd[S]=pre1,hd[T]=pre2,hd[b1]=pre3,hd[b2]=pre4;
61         adde(S,b2,bn);adde(b1,T,bn);
62         puts(dinic()==an+bn?"Yes":"No"); 
63     }
64     return 0; 
65 } 
66 
67 
68 
69 
70 
71 
72 
73 //一个比较巧妙的路径；
74 //通过yy可以发现，将第二条路径反向再做一遍就可以避免错误；
75 //20181210
76 
77 
78

View Code

bzoj2039[2009国家集训队]employee

题解：首先<i,T,Ai>表示是否选择购买，考虑每对经理(i,j) , <S,i,Ei,j> <S,j,Ei,j> <i,j,2*Ei,j> ，这个网络可以化简：<S,i,$sum_{j}Ei,j$> <i,T,Ai> <i,j,2*Ei,j>，假设最小割为C，E的和为Sum，ans = 2*Sum – C;

 1 #include<bits/stdc++.h>
 2 #define ll long long 
 3 #define inf 1e18
 4 using namespace std;
 5 const int N=1010,M=2000010;
 6 int n,o,hd[N],vis[N],d[N],cur[N];
 7 struct Edge{int v,nt; ll c,f;}E[M<<1];
 8 char gc(){
 9     static char*p1,*p2,s[1000000];
10     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
11     return(p1==p2)?EOF:*p1++;
12 }
13 ll rd(){
14     ll x=0; char c=gc();
15     while(c<'0'||c>'9')c=gc();
16     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
17     return x;
18 }
19 void adde(int u,int v,ll c){
20     E[o]=(Edge){v,hd[u],c,0};hd[u]=o++;
21     E[o]=(Edge){u,hd[v],0,0};hd[v]=o++;
22 }
23 queue<int>q;
24 bool bfs(){
25     for(int i=0;i<=n+1;i++)vis[i]=d[i]=0;
26     vis[0]=d[0]=1;q.push(0);
27     while(!q.empty()){
28         int u=q.front();q.pop();
29         for(int i=hd[u],v;~i;i=E[i].nt)if(E[i].c>E[i].f){
30             if(!vis[v=E[i].v])vis[v]=1,d[v]=d[u]+1,q.push(v);
31         }
32     }
33     return vis[n+1];
34 }
35 ll dfs(int u,ll F){
36     if(u==n+1||!F)return F;
37     int flow=0,f;
38     for(int i=cur[u];~i;i=E[i].nt){
39         int v=E[cur[u]=i].v;
40         if(d[v]==d[u]+1&&(f=dfs(v,min(E[i].c-E[i].f,F)))){
41             flow+=f,F-=f;
42             E[i].f+=f,E[i^1].f-=f;
43             if(!F)break;
44         }
45     }
46     return flow;
47 }
48 int dinic(){
49     int flow=0,f;
50     while(bfs()){
51         for(int i=0;i<=n+1;i++)cur[i]=hd[i];
52         while(f=dfs(0,inf))flow+=f;
53     }
54     return flow;
55 }
56 int main(){
57     freopen("bzoj2039.in","r",stdin);
58     freopen("bzoj2039.out","w",stdout);
59     n=rd();for(int i=0;i<=n+1;i++)hd[i]=-1;
60     for(int i=1;i<=n;i++)adde(i,n+1,rd());
61     ll ans=0;
62     for(int i=1;i<=n;i++){
63         ll sum=0,x;    
64         for(int j=1;j<=n;j++){
65             x=rd();sum+=x;
66             adde(i,j,x<<1);
67         }
68         adde(0,i,sum);
69         ans+=sum;
70     }
71     ans-=dinic(); 
72     printf("%lld
",ans);
73     return 0;
74 }
75 
76 
77 
78 
79 
80 
81 
82 
83 
84 
85 
86 //这题卡常？？？？
87 //luogu的我没过，开了O(2)好像也不行，bzoj勉强过了。。。。；
88 //(S,i,sum ei,j) (i,j,2*ei,j) (i,T,ai)
89 //20181210 
90 
91 
92 
93

View Code

bzoj1797[AHOI2009]mincut

题解：

先做一遍最大流，考虑残量网络(要考虑反向边)，

如果一条边有可能不满流那么它一定不可能为任何个割的一部分，一定满流那么它一定为某个割的一部分；

考虑一个最小割对应的划分集合S集合T集，跨越ST集合的边为割，那么残网中一定只存在T->S的边，假设存在S-T的边，要么为某个S->T的正向边要么为某个T->S反向边，前者不符合割后者不符合最小（感性理解吧。。。。）；

所以在残网中做scc，设i所在scc为bl[i] , 首先bl[S]!=bl[T],对于残网中的边(u,v)：

①如果bl[u]==bl[v]，一定不可能为割边

②如果bl[u]!=bl[v]且bl[u]==bl[T]&&bl[v]==bl[S],则一定为割边，否则在缩点后的残网DAG上一定可以有一个另外的割；

  1 #include<bits/stdc++.h>
  2 #define inf 0x3f3f3f3f
  3 using namespace std;
  4 const int N=4010,M=60010;
  5 int S,T,n,m,o,hd[N],cur[N],vis[N],d[N],dfn[N],low[N],idx,bl[N],cnt;
  6 struct Edge{int u,v,nt,c,f;}E[M<<1];
  7 void adde(int u,int v,int c){
  8     E[o]=(Edge){u,v,hd[u],c,0};hd[u]=o++;
  9     E[o]=(Edge){v,u,hd[v],0,0};hd[v]=o++;
 10 }
 11 queue<int>q;
 12 bool bfs(){
 13     for(int i=1;i<=n;i++)vis[i]=d[i]=0;
 14     vis[S]=d[S]=1;q.push(S);
 15     while(!q.empty()){
 16         int u=q.front();q.pop();
 17         for(int i=hd[u],v;~i;i=E[i].nt)if(E[i].c>E[i].f){
 18             if(!vis[v=E[i].v])vis[v]=1,d[v]=d[u]+1,q.push(v);
 19         }
 20     }
 21     return vis[T];
 22 }
 23 int dfs(int u,int F){
 24     if(u==T||!F)return F;
 25     int flow=0,f;
 26     for(int i=cur[u];~i;i=E[i].nt){
 27         int v=E[cur[u]=i].v;
 28         if(d[v]==d[u]+1&&(f=dfs(v,min(F,E[i].c-E[i].f)))){
 29             flow+=f,F-=f;
 30             E[i].f+=f,E[i^1].f-=f;
 31             if(!F)break;
 32         }
 33     }
 34     return flow;
 35 }
 36 int dinic(){
 37     int flow=0;
 38     while(bfs()){
 39         for(int i=1;i<=n;i++)cur[i]=hd[i];
 40         flow+=dfs(S,inf);
 41     }
 42     return flow;
 43 }
 44 stack<int>s;
 45 void tarjan(int u){
 46     dfn[u]=low[u]=++idx;
 47     s.push(u);
 48     for(int i=hd[u];~i;i=E[i].nt)if(E[i].c>E[i].f){
 49         int v=E[i].v;
 50         if(dfn[v]){if(!d[v])low[u]=min(dfn[v],low[u]);}
 51         else {tarjan(v);low[u]=min(low[v],low[u]);}
 52     }
 53     if(dfn[u]==low[u]){
 54         int v;++cnt;
 55         do{
 56             v=s.top();s.pop();
 57             d[v]=1;bl[v]=cnt;
 58         }while(v!=u);
 59     }
 60 }
 61 int main(){
 62     freopen("bzoj1797.in","r",stdin);
 63     freopen("bzoj1797.out","w",stdout);
 64     scanf("%d%d%d%d",&n,&m,&S,&T);
 65     for(int i=1;i<=n;i++)hd[i]=-1;
 66     for(int i=1,u,v,c;i<=m;i++){
 67         scanf("%d%d%d",&u,&v,&c);
 68         adde(u,v,c);
 69     }
 70     dinic();
 71     for(int i=1;i<=n;i++)d[i]=0;
 72     for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
 73     for(int i=0;i<o;i+=2){
 74         int u=E[i].u,v=E[i].v;
 75         if(E[i].f!=E[i].c){puts("0 0");continue;}
 76         putchar(bl[u]==bl[v]?'0':'1');
 77         puts(bl[u]==bl[S]&&bl[v]==bl[T]?" 1":" 0");
 78     }
 79     return 0;
 80 }
 81 
 82 
 83 
 84 
 85 
 86 
 87 
 88 
 89 
 90 
 91 //首先做一遍最大流；
 92 //可以证明，可能不满流的边一定不在任何最小割上，而一定满流的边一定在某个最小割上；(虽然对这个题用处不大)
 93 //考虑残量网络（包括不满的边和反向边）
 94 //最小割和一个ST划分sS,tT且只有跨越T到S的边一一对应
 95 //(这个我还不能得出一个完整的说明，但是参考定义讨论划分跨越S到T的边可以粗略理解)
 96 //所以scc里的边一定不是；
 97 //缩点成DAG；DAG的割和原图的割对应； 
 98 //除非某条边直接连接了s和t，即u和s属于同一个scc，v和t也同，否则一定有一种不包含这条边的割；
 99 //艰难地想到了第一问，第二问完全懵逼；
100 //20181211
101 
102  
103 
104 
105 
106  
107 
108 
109

View Code

bzoj3158 千钧一发

题解：考虑ai,aj均为奇数，令ai=2k1+1,aj=2k2+1,画一画ai^2+aj^2发现不满足①，考虑ai,aj都为偶数，显然不满足②，于是奇偶二分转成最小割做就好；

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 #define ll long long 
 4 using namespace std;
 5 const int N=3010,M=1000010;
 6 int n,A[N],B[N],o,hd[N],cur[N],vis[N],d[N];
 7 struct Edge{int v,nt,c,f;}E[M<<1];
 8 int gcd(int a,int b){return !b?a:gcd(b,a%b);}
 9 bool judge(int i,int j){
10     if(gcd(A[i],A[j])!=1)return false;
11     ll v = (ll)A[i]*A[i]+(ll)A[j]*A[j];
12     ll t = floor(sqrt(1.0*v)+0.5); 
13     return v==t*t;
14 }
15 void adde(int u,int v,int c){
16     E[o]=(Edge){v,hd[u],c,0};hd[u]=o++;
17     E[o]=(Edge){u,hd[v],0,0};hd[v]=o++;
18 }
19 queue<int>q;
20 bool bfs(){
21     for(int i=0;i<=n+1;i++)vis[i]=d[i]=0;
22     vis[0]=d[0]=1;q.push(0);
23     while(!q.empty()){
24         int u=q.front();q.pop();
25         for(int i=hd[u],v;~i;i=E[i].nt)if(E[i].c>E[i].f){
26             if(!vis[v=E[i].v])vis[v]=1,d[v]=d[u]+1,q.push(v);
27         }
28     }
29     return vis[n+1];
30 }
31 int dfs(int u,int F){
32     if(u==n+1||!F)return F;
33     int flow=0,f;
34     for(int i=cur[u];~i;i=E[i].nt){
35         int v=E[cur[u]=i].v;
36         if(d[v]==d[u]+1&&(f=dfs(v,min(E[i].c-E[i].f,F)))){
37             flow+=f,F-=f;
38             E[i].f+=f,E[i^1].f-=f; 
39             if(!F)break;
40         }
41     }
42     return flow;
43 }
44 int main(){
45 //    freopen("bzoj3158.in","r",stdin);
46 //    freopen("bzoj3158.out","w",stdout);
47     scanf("%d",&n);
48     for(int i=0;i<=n+1;i++)hd[i]=-1;
49     for(int i=1;i<=n;i++)scanf("%d",&A[i]);
50     int ans=0;
51     for(int i=1;i<=n;i++)B[i]=A[i],/*scanf("%d",&B[i]),*/ans+=B[i];
52     for(int i=1;i<=n;i++){
53         (A[i]&1)?adde(0,i,B[i]):adde(i,n+1,B[i]);
54         if(A[i]&1){
55             for(int j=1;j<=n;j++)if(judge(i,j))adde(i,j,inf);
56         }
57     } 
58     while(bfs()){for(int i=0;i<=n+1;i++)cur[i]=hd[i];ans-=dfs(0,inf);}
59     printf("%d
",ans);
60     return 0;
61 }//by tkys_Austin; 
62 
63 
64 
65 
66 
67 
68 
69 
70 
71 
72 //发现自己最近越来越弱。。。。
73 //奇数和奇数满足1，偶数和偶数满足2；
74 //二分图最大点权独立集转最小割即可；
75 //20181211 
76 
77 
78 
79

View Code

bzoj4514[sdoi2016]数字配对

题解：由于ai/aj为质数，所以一定没有可配对关系的奇环，染色变成二分图和上一题一样建图，做费用流直到费用为负；

  1 #include<bits/stdc++.h>
  2 #define inf 1e18
  3 #define rg register 
  4 #define Run(i,l,r) for(int i=l;i<=r;i++)
  5 #define il inline 
  6 #define ll long long 
  7 using namespace std;
  8 const int N=210,M=50010;
  9 int n,pri[100010],vis[100010],cnt,o,hd[N],col[N],a[N],b[N],c[N];
 10 ll dis[N];
 11 vector<int>g[N];
 12 struct Edge{int v,nt,f;ll w;}E[M<<1];
 13 il void Adde(int u,int v){
 14     g[u].push_back(v);
 15     g[v].push_back(u);
 16 }
 17 il void adde(int u,int v,int f,ll w){
 18     E[o]=(Edge){v,hd[u],f,w};hd[u]=o++;
 19     E[o]=(Edge){u,hd[v],0,-w};hd[v]=o++;
 20 }
 21 bool judge(int i,int j){
 22     if(a[i]<a[j])swap(i,j);
 23     if(a[i]%a[j])return false;
 24     int t=a[i]/a[j];
 25     for(int k=1;pri[k]*pri[k]<=t;k++)if(!(t%pri[k]))return false;
 26     return true;
 27 }
 28 il void Dfs(int u){
 29     vis[u]=1;
 30     Run(i,0,(int)g[u].size()-1){
 31         int v=g[u][i];
 32         if(vis[v])continue;
 33         col[v]=col[u]^1;
 34         Dfs(v);
 35     }
 36 }
 37 queue<int>q;
 38 bool bfs(){
 39     Run(i,0,n+1)vis[i]=0,dis[i]=inf;
 40     dis[n+1]=0,vis[n+1]=1;q.push(n+1);
 41     while(!q.empty()){
 42         int u=q.front();q.pop();
 43         vis[u]=0;
 44         for(int i=hd[u];~i;i=E[i].nt)if(E[i^1].f){
 45             int v=E[i].v;
 46             if(dis[v]>dis[u]+E[i^1].w){
 47                 dis[v]=dis[u]+E[i^1].w;
 48                 if(!vis[v])vis[v]=1,q.push(v);
 49             }
 50         }
 51     }
 52     return dis[0]!=inf;
 53 }
 54 int dfs(int u,int F){
 55     vis[u]=1;
 56     if(u==n+1||!F)return F;
 57     int flow=0,f;
 58     for(int i=hd[u];~i;i=E[i].nt){
 59         int v=E[i].v;
 60         if(!vis[v]&&dis[v]+E[i].w==dis[u]&&E[i].f&&(f=dfs(v,min(F,E[i].f)))){
 61             flow+=f,F-=f;
 62             E[i].f-=f,E[i^1].f+=f;
 63             if(!F)break;
 64         }
 65     }
 66     return flow;
 67 }
 68 int main(){
 69     freopen("bzoj4514.in","r",stdin);
 70     freopen("bzoj4514.out","w",stdout);
 71     memset(hd,-1,sizeof(hd));
 72     for(int i=2;i<=1e5;i++){
 73         if(!vis[i])pri[++cnt]=i;
 74         for(int j=1;j<=cnt&&i*pri[j]<=1e5;j++){
 75             vis[i*pri[j]]=0;
 76             if(i%pri[j]==0)break;
 77         }
 78     }
 79     scanf("%d",&n);
 80     Run(i,1,n)scanf("%d",&a[i]);
 81     Run(i,1,n)scanf("%d",&b[i]);
 82     Run(i,1,n)scanf("%d",&c[i]);
 83     Run(i,1,n)Run(j,1,n)if(i!=j&&judge(i,j))Adde(i,j);
 84     Run(i,1,n)vis[i]=0;
 85     Run(i,1,n)if(!vis[i])Dfs(i);
 86     Run(i,1,n)if(!col[i]){
 87         adde(0,i,b[i],0);
 88         Run(j,0,(int)g[i].size()-1){
 89             adde(i,g[i][j],1e9,-(ll)c[i]*c[g[i][j]]);
 90         }
 91     }else adde(i,n+1,b[i],0);
 92     int ans=0;ll now=0;int fg=0;
 93     while(bfs()){
 94         do{
 95             for(int i=0;i<=n+1;i++)vis[i]=0;
 96             int tmp=dfs(0,1e9);
 97             if(tmp*dis[0]+now>0){
 98                 ans+=-now/dis[0];
 99                 fg=1;
100                 break;
101             }
102             now+=tmp*dis[0];
103             ans+=tmp;
104         }while(vis[n+1]);
105         if(fg)break;
106     }
107     printf("%d
",ans);
108     return 0;
109 } 
110 
111 
112 
113 
114 
115 
116 
117 
118 //由于必定是质数倍数，所以不可能存在奇环；
119 //建二分图跑费用流直到费用为负值；
120 //20181214
121 
122 
123  
124 
125

View Code

bzoj1061 [Noi2008]志愿者招募

题解：

orz byvoid

https://www.byvoid.com/zhs/blog/noi-2008-employee

还有一种上下界的做法：

https://www.cnblogs.com/nietzsche-oier/p/8205275.html

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 const int N=1010,M=20010;
 5 int n,m,d[N],S,T,o,hd[N],vis[N],pre[N],dis[N];
 6 struct Edge{int u,v,nt,c,f,w;}E[M<<1];
 7 void adde(int u,int v,int c,int w){
 8     E[o]=(Edge){u,v,hd[u],c,0,w};hd[u]=o++;
 9     E[o]=(Edge){v,u,hd[v],0,0,-w};hd[v]=o++;
10 }
11 queue<int>q;
12 bool spfa(){
13     for(int i=S;i<=T;i++)vis[i]=0,pre[i]=-1,dis[i]=inf;
14     vis[S]=1,dis[S]=0;q.push(S);
15     while(!q.empty()){
16         int u=q.front();q.pop();
17         vis[u]=0;
18         for(int i=hd[u];~i;i=E[i].nt)if(E[i].c>E[i].f){
19             int v=E[i].v;
20             if(dis[v]>dis[u]+E[i].w){
21                 dis[v]=dis[u]+E[pre[v]=i].w;
22                 if(!vis[v])vis[v]=1,q.push(v);
23             }
24         }
25     }
26     return ~pre[T];
27 }
28 int MCMF(){
29     int cost=0;
30     while(spfa()){
31         int mn=inf;
32         for(int u=T;u!=S;u=E[pre[u]].u)mn=min(E[pre[u]].c-E[pre[u]].f,mn);
33         for(int u=T;u!=S;u=E[pre[u]].u)E[pre[u]].f+=mn,E[pre[u]^1].f-=mn;
34         cost+=mn*dis[T];
35     }
36     return cost;
37 }
38 int main(){
39     freopen("bzoj1061.in","r",stdin);
40     freopen("bzoj1061.out","w",stdout);
41     scanf("%d%d",&n,&m);
42     S=0,T=n+2;for(int i=S;i<=T;i++)hd[i]=-1;
43     for(int i=1;i<=n;i++)scanf("%d",&d[i]);
44     for(int i=1;i<=n+1;i++){
45         if(d[i]>d[i-1])adde(S,i,d[i]-d[i-1],0); 
46         else adde(i,T,d[i-1]-d[i],0);
47         if(i<=n)adde(i+1,i,inf,0); 
48     }
49     for(int i=1,s,t,c;i<=m;i++){
50         scanf("%d%d%d",&s,&t,&c);
51         adde(s,t+1,inf,c);
52     }
53     int ans = MCMF();
54     printf("%d
",ans);
55     return 0;
56 }
57 
58 
59 
60 
61 
62 
63 
64 
65 
66 //这建图，给跪了ORZ；
67 //不会单纯形，但是似乎这类都可以费用流做；
68 //https://www.byvoid.com/zhs/blog/noi-2008-employee
69 //这题似乎还可以上下界费用流：
70 //https://www.cnblogs.com/nietzsche-oier/p/8205275.html 
71 //20181212
72 
73  
74 
75 
76

View Code

bzoj3876 [AHOI2014&JSOI2014]支线剧情

题解：令原图中的边有一个流量下界1，再把所有点都连回1号点，就是裸的上下界网络流了；

叙述几种比较经典的：设上界为c , 下界为b
①无源无汇的上下界可行流：考虑下界全满，每条边的下界总入流-下界总出流 > 0则从S加边，反之加边到T，原图中的边流量上界变为c-b,S到T满流即有可行流，实际流量加上b即可；

②有源有汇的上下界可行流：如果原图中源点为s，汇点为t，从t到s建一条上下界无限制的边，就变成了①，同时可以发现这条边的流量就是整个网络的流量；

③有源有汇的上下界最大流/最小流：
最大流：建图如①，S-T最大流不一定是原图最大，利用增广路的可加性再从s到t做最大流即可，同时(t,s)的反向边退流之后自动将第一次的流量加到答案中了；

最小流：建图如①，S-T最大流不一定是原图最小，因为有可能有循环流没有利用，

两种方法，

一是注意在②里提到的性质，先不加(t,s)边做S->T的最大流，让流量尽量往其它边分配(我也说不清楚。。)，再加上(t,s)边做一遍；

二是加上(t,s)，先做S->T，然后从t->s做最大流尽量退流然后减去这部分流量；

④上述问题的费用流表述：大多都直接套个费用流

 1 上下界网络流：
 2 -------------------------------------------------------------------------------
 3 这篇论文较为清晰：
 4 
 5 https://wenku.baidu.com/view/042856687e21af45b307a875.html?rec_flag=default&sxts=1544613394871
 6 
 7 这篇论文里有一个比较好的例子：
 8 
 9 https://wenku.baidu.com/view/f751ee6d27d3240c8447ef28.html
10 
11 这篇博客挺全：
12 
13 https://blog.csdn.net/clove_unique/article/details/54884437
14 
15 大致就这几种比较正常的：
16 无源汇的上下界可行流；
17 有源汇的上下界可行流/最大流/最小流；
18 上述问题的费用流表述；
19 
20 题目：
21 模板：loj115-117
22 （全部权限题。。。。。）
23 bzoj2502
24 bzoj3876 
25 bzoj2055
26 bzoj3698
27 -------------------------------------------

上下界网络流资料整理

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 #define mk make_pair
 4 #define fir first
 5 #define sec second 
 6 using namespace std;
 7 const int N=310,M=6010;
 8 char gc(){
 9     static char*p1,*p2,s[1000000];
10     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
11     return(p1==p2)?EOF:*p1++;
12 }
13 int rd(){
14     int x=0;char c=gc();
15     while(c<'0'||c>'9')c=gc();
16     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
17     return x;
18 }
19 int S,T,n,m,vis[N],pre[N],o,hd[N],dis[N],d[N];
20 typedef pair<int,int>pii;
21 vector<pii>g[N];
22 queue<int>q;
23 struct Edge{int u,v,nt,c,f,w;}E[M<<1];
24 void adde(int u,int v,int c,int w){
25     E[o]=(Edge){u,v,hd[u],c,0,w};hd[u]=o++;
26     E[o]=(Edge){v,u,hd[v],0,0,-w};hd[v]=o++;
27 }
28 bool spfa(){
29     for(int i=S;i<=T;i++)dis[i]=inf,vis[i]=0,pre[i]=-1;
30     dis[S]=0;vis[S]=1;q.push(S);
31     while(!q.empty()){
32         int u=q.front();q.pop();
33         vis[u]=0;
34         for(int i=hd[u];~i;i=E[i].nt)if(E[i].c>E[i].f){
35             int v=E[i].v;
36             if(dis[v]>dis[u]+E[i].w){
37                 dis[v]=dis[u]+E[pre[v]=i].w;
38                 if(!vis[v])vis[v]=1,q.push(v);
39             }
40         }
41     }
42     return ~pre[T];
43 }
44 int MCMF(){
45     int cost=0;
46     while(spfa()){
47         int mn=inf;
48         for(int u=T;u!=S;u=E[pre[u]].u)mn=min(mn,E[pre[u]].c-E[pre[u]].f);
49         for(int u=T;u!=S;u=E[pre[u]].u)E[pre[u]].f+=mn,E[pre[u]^1].f-=mn;
50         cost+=mn*dis[T];
51     }
52     return cost;
53 }
54 int main(){
55     freopen("bzoj3876.in","r",stdin);
56     freopen("bzoj3876.out","w",stdout);
57     n=rd();
58     S=0,T=n+1;
59     for(int i=S;i<=T;i++)hd[i]=-1;
60     int ans=0;
61     for(int i=1;i<=n;i++){
62         m=rd();
63         for(int j=1,x,y;j<=m;j++){
64             x=rd();y=rd();
65             adde(i,x,inf,y);
66             d[i]--,d[x]++;
67             ans+=y;
68         }
69         if(i!=1)adde(i,1,inf,0);
70     }
71     for(int i=1;i<=n;i++)if(d[i]>0)adde(S,i,d[i],0);
72     else adde(i,T,-d[i],0);
73     ans+=MCMF();
74     printf("%d
",ans);
75     return 0;
76 }

View Code

bzoj1070 [scoi2007]修车

题解:考虑技术人员j倒数第k个修的车为i花费为k*a[i][j]，流和方案不一一对应，但是最优方一定对应，这样对技术人员拆点做完美匹配即可；

为了卡常还特意学了学zkw费用流，最后却发现是(我太蠢了)我板子太low了，多了一个变量c导致常数巨大，上面的代码都是这样，千万不要学；

  1 #include<bits/stdc++.h>
  2 #define inf 0x7fffffff
  3 using namespace std;
  4 const int N=1010,M=60010,sz=1010;
  5 int n,m,S,T,o,t[110][50],hd[N],vis[N],dis[N];
  6 int ans;
  7 int q[N],head,tail;
  8 struct Edge{int u,v,nt,f,w;}E[M<<1];
  9 void adde(int u,int v,int c,int w){
 10     E[o]=(Edge){u,v,hd[u],c,w};hd[u]=o++;
 11     E[o]=(Edge){v,u,hd[v],0,-w};hd[v]=o++;
 12 }
 13 bool spfa(){
 14     memset(vis,0,sizeof(vis));
 15     for(int i=0;i<=T;i++)dis[i]=inf,vis[i]=0;
 16     vis[T]=1,dis[T]=0;
 17     head=0,tail=1;q[0]=T;
 18     while(head!=tail){
 19         int u=q[head];if(++head==T)head=0;
 20         vis[u]=0;
 21         for(int i=hd[u];~i;i=E[i].nt)if(E[i^1].f){
 22             int v=E[i].v;
 23             if(dis[v]>dis[u]+E[i^1].w){
 24                 dis[v]=dis[u]+E[i^1].w;
 25                 if(!vis[v]){vis[v]=1;q[tail++]=v;if(tail==T)tail=0;}
 26             }
 27         }
 28     }
 29     return dis[S]!=inf;
 30 } 
 31 int dfs(int u,int F){
 32     vis[u]=1;
 33     if(u==T||!F)return F;
 34     int flow=0,f;
 35     for(int i=hd[u];~i;i=E[i].nt){
 36         int v=E[i].v;
 37         if(E[i].f&&dis[u]==dis[v]+E[i].w&&!vis[v]&&(f=dfs(v,min(F,E[i].f)))){
 38             flow+=f,F-=f;
 39             E[i].f-=f,E[i^1].f+=f;
 40             //ans+=E[i].w*f;
 41             if(!F)break;
 42         }
 43     }
 44     return flow;
 45 }
 46 int zkw(){
 47     int cost=0;
 48     while(spfa()){
 49         vis[T]=1;
 50         while(vis[T]){
 51             memset(vis,0,sizeof(vis));
 52             cost+=dis[S]*dfs(S,inf);
 53         }
 54     }
 55     return cost;
 56 }
 57 char gc(){
 58     static char*p1,*p2,s[1000000];
 59     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
 60     return(p1==p2)?EOF:*p1++;
 61 }
 62  int rd(){
 63     int x=0; char c=gc();
 64     while(c<'0'||c>'9')c=gc();
 65     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
 66     return x;
 67 }
 68 int main(){
 69     freopen("bzoj1070.in","r",stdin);
 70     freopen("bzoj1070.out","w",stdout);
 71     m=rd();n=rd();
 72     for(int i=1;i<=n;i++)
 73     for(int j=1;j<=m;j++)t[i][j]=rd();
 74     S=0,T=(m+1)*n+1;
 75     for(int i=S;i<=T;i++)hd[i]=-1;
 76     for(int i=1;i<=n;i++){
 77         adde(i,T,1,0);    
 78         for(int j=1;j<=m;j++){
 79             adde(S,j*n+i,1,0);     
 80             for(int k=1;k<=n;k++){
 81                 adde(j*n+i,k,1,i*t[k][j]);
 82             } 
 83         } 
 84     }
 85     ans =zkw();
 86     printf("%.2lf
",1.0*ans/n);
 87     return 0;
 88 }
 89 
 90 
 91 
 92 
 93 
 94 
 95 
 96 
 97 
 98 //经过一个上午艰辛地验证（TAT）终于把网络流实现的常数问题弄清楚了；
 99 //zkw费用流和它的spfa版可能效率差别不大，但是在边权小，流量大的情况下比EK要好很多； 
100 //zkw费用流的spfa中间要有两个while，尽量减少spfa的次数；
101 //倒着跑T->S，使得更多的最短路径指向T;
102 //网络流存边不要使用c，直接用f即可（所以模板有很多要修改的地方）
103 //用Edge{..}加边不会影响效率，但是尽量少嵌套引用；
104 //zkw费用流dfs实现的时候注意一定要有流量才可以dfs过去，dinic无所谓，但是由于zkw记录了vis，所以会死循环；
105 //T了一版，代价有点大 
106 //20181213 
107 
108 
109 
110 
111 
112 
113

spfa版zkw

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 #define il inline 
 4 #define rg register 
 5 using namespace std;
 6 const int N=1010,M=60010;
 7 int n,m,S,T,o,t[110][50],hd[N],vis[N],d[N];
 8 struct Edge{int u,v,nt,c,f,w;}E[M<<1];
 9 il void adde(int u,int v,int c,int w){
10 //    printf("%d %d %d %d
",u,v,c,w);
11     E[o]=(Edge){u,v,hd[u],c,0,w};hd[u]=o++;
12     E[o]=(Edge){v,u,hd[v],0,0,-w};hd[v]=o++;
13 }
14 il char gc(){
15     static char*p1,*p2,s[1000000];
16     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
17     return(p1==p2)?EOF:*p1++;
18 }
19 il int rd(){
20     int x=0; char c=gc();
21     while(c<'0'||c>'9')c=gc();
22     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
23     return x;
24 }
25 int dfs(int u,int F){
26     vis[u]=1;
27     if(u==T||!F)return F;
28     int flow=0,f;
29     for(int i=hd[u];~i;i=E[i].nt){
30         int v=E[i].v;
31     //    printf("%d %d
",u,v);
32         if(!vis[v]&&E[i].c>E[i].f&&d[u]+E[i].w-d[v]==0&&(f=dfs(v,min(E[i].c-E[i].f,F)))){
33             flow+=f,F-=f;
34             E[i].f+=f,E[i^1].f-=f;
35             if(!F)break;
36         }
37     }
38     return flow;
39 }
40 bool mdf(){
41     if(vis[T])return true;
42     int mn=inf;
43     for(int i=0;i<o;i++){
44         int u=E[i].u,v=E[i].v;
45         if(E[i].c>E[i].f&&vis[u]&&!vis[v])mn=min(mn,d[u]+E[i].w-d[v]);
46     }
47     if(mn==inf)return false;
48     for(int i=S;i<=T;i++)if(vis[i])d[i]-=mn;
49     return true;
50 }
51 int zkw(){
52     int cost=0;
53     do{
54         for(int i=S;i<=T;i++)vis[i]=0;
55         cost-=d[S]*dfs(S,inf);
56     }
57     while(mdf());
58     return cost;
59 }
60 int main(){
61     freopen("bzoj1070.in","r",stdin);
62     freopen("bzoj1070.out","w",stdout);
63     m=rd();n=rd();
64     for(rg int i=1;i<=n;i++)
65     for(rg int j=1;j<=m;j++)t[i][j]=rd();
66     S=0,T=(m+1)*n+1;
67     for(rg int i=S;i<=T;i++)hd[i]=-1;
68     for(rg int i=1;i<=n;i++){
69         adde(i,T,1,0);    
70         for(rg int j=1;j<=m;j++){
71             adde(S,j*n+i,1,0);     
72             for(rg int k=1;k<=n;k++){
73                 adde(j*n+i,k,1,i*t[k][j]);
74             } 
75         } 
76     }
77     int ans = zkw();
78     printf("%.2lf
",1.0*ans/n);
79     return 0;
80 }

正版zkw

bzoj2879[Noi2012]美食节

题解：一样的只不过数据范围变大，EK算法每次增广之后记录增广的是哪个厨师的第倒数第几个，假设i的倒数第j个，这样再将(i,j+1)点加入图中（其实这种方法还挺常见）

 1 #include<bits/stdc++.h>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 const int N=101000,M=4100000;
 5 int n,m,o,hd[N],dis[N],pre[N],vis[N],sum,S,T,p[50],t[50][210];
 6 struct Edge{int u,v,nt,f,w;}E[M<<1];
 7 void adde(int u,int v,int f,int w){
 8     E[o]=(Edge){u,v,hd[u],f,w};hd[u]=o++;
 9     E[o]=(Edge){v,u,hd[v],0,-w};hd[v]=o++;
10 }
11 //queue<int>q;
12 int head,tail,q[N];
13 bool spfa(){
14     for(int i=S;i<=T;i++)dis[i]=inf;
15 //    memset(pre,-1,sizeof(pre));
16 //    memset(dis,0x3f,sizeof(dis));
17     vis[S]=1,dis[S]=0;//q.push(S);
18     head=0;tail=1;q[0]=0; 
19     int C=0;
20     while(head!=tail/*!q.empty()*/){
21 //        C++;
22         //int u=q.front();q.pop();
23         int u=q[head];if(++head==T)head=0;
24         vis[u]=0;
25         for(int i=hd[u];~i;i=E[i].nt)if(E[i].f){
26             int v=E[i].v;
27             if(dis[v]>dis[u]+E[i].w){
28                 dis[v]=dis[u]+E[pre[v]=i].w;
29                 if(!vis[v]){
30                     q[tail]=v;if(++tail==T)tail=0;
31                     vis[v]=1;
32                 }//q.push(v),vis[v]=1;
33             } 
34         }
35     }
36 //    printf("%d
",C);
37     return dis[T]!=inf;//~pre[T];
38 }
39 int EK(){
40     int cost=0,flow=0;
41     while(spfa()){
42     //    printf("%d %d
",cost,o);
43         int /*mn=inf,*/a,b;
44         for(int u=T;u;u=E[pre[u]].u){
45         //    mn=min(mn,E[pre[u]].f);
46             if(u<=sum*m){a = (u - 1) / m + 1 , b = (u - 1) % m + 1;} 
47             E[pre[u]].f-=1,E[pre[u]^1].f+=1;
48         }
49     //    for(int u=T;u;u=E[pre[u]].u)E[pre[u]].f-=mn,E[pre[u]^1].f+=mn;
50         cost+=dis[T];//*mn;
51         flow+=1;
52         adde(S,a*m+b,1,0);
53         for(int i=1;i<=n;i++)adde(a*m+b,sum*m+i,1,(a+1)*t[i][b]);
54         if(sum==flow)break;
55     }
56     return cost;
57 }
58 int main(){
59     freopen("bzoj2879.in","r",stdin);
60     freopen("bzoj2879.out","w",stdout);
61     scanf("%d%d",&n,&m);
62     for(int i=1;i<=n;i++){scanf("%d",&p[i]);sum+=p[i];}
63     S=0,T=sum*m+n+1;
64     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&t[i][j]);
65     memset(hd,-1,sizeof(hd));
66     for(int i=1;i<=m;i++){
67         adde(S,i,1,0);
68         for(int j=1;j<=n;j++)adde(i,sum*m+j,1,t[j][i]); 
69     }
70     for(int i=1;i<=n;i++)adde(sum*m+i,T,p[i],0);
71     int ans = EK();
72     printf("%d
",ans);
73     return 0;
74 }
75 
76 
77 
78 
79 
80 
81 
82  
83 
84 
85 
86 
87 //和修车差不多；
88 //这里有个很小但是很致命的优化：
89 //利用EK的特点，动态加边；
90 //注意不能判断某道菜被做完了就不加边，因为可能会撤编？？？ 
91 //如果sum==flow时就break；否则会把很多时间花费判断没有增广路上； 
92 //ORZ
93 //大致时间复杂度O(p^2 n)； 
94 
95

View Code

bzoj1449[JSoi2009]球队收益

题解：发现直接利用费用不太好计算变化，考虑所有队都输了，可以计算出此时每个队的收益，同时可以计算出每个队i又多赢了j场的在多赢了j-1场的基础上增加的收益dij，剩下的就简单了：对每场比赛(ai,bi) 建边<S,i,1,0> <i,ai,1,0> <i,bi,1,0>为球队分配胜场，对每个队i建边<i,T,inf,dij>表示增加收益；由于di,j+1>=di,j所以直接做最小费用最大流是没问题的；

 1 #include<bits/stdc++.h>
 2 #define inf 0x7fffffff
 3 using namespace std;
 4 const int N=6010;
 5 int n,m,o,hd[N],vis[N],pre[N],dis[N],d[N],X[N],Y[N],C[N],D[N],a[N];
 6 struct Edge{int u,v,nt,f,w;}E[N<<1];
 7 int cal(int i){return C[i]*X[i]*X[i]+D[i]*Y[i]*Y[i];}
 8 queue<int>q;
 9 void adde(int u,int v,int f,int w){
10     E[o]=(Edge){u,v,hd[u],f,w};hd[u]=o++;
11     E[o]=(Edge){v,u,hd[v],0,-w};hd[v]=o++;
12 }
13 bool spfa(){
14     for(int i=0;i<=n+m+1;i++)dis[i]=inf;
15     dis[0]=0;vis[0]=1;q.push(0);
16     while(!q.empty()){
17         int u=q.front();q.pop();
18         vis[u]=0;
19         for(int i=hd[u];~i;i=E[i].nt)if(E[i].f){
20             int v=E[i].v;
21             if(dis[v]>dis[u]+E[i].w){
22                 dis[v]=dis[u]+E[pre[v]=i].w;
23                 if(!vis[v])vis[v]=1,q.push(v);
24             }
25         }
26     } 
27     return dis[n+m+1]!=inf;
28 }
29 int EK(){
30     int cost=0,u,t;
31     while(spfa()){
32         for(u=n+m+1;u;u=E[pre[u]].u)E[pre[u]].f--,E[pre[u]^1].f++;
33         cost+=dis[n+m+1];
34         u=E[pre[n+m+1]].u-m;
35         if(d[u]--){
36             X[u]++,Y[u]--;
37             t=a[u];a[u]=cal(u);
38             adde(u+m,n+m+1,1,a[u]-t);
39         }
40     }
41     return cost;
42 }
43 int main(){
44     freopen("bzoj1449.in","r",stdin);
45     freopen("bzoj1449.out","w",stdout);
46     scanf("%d%d",&n,&m);
47     memset(hd,-1,sizeof(hd)); 
48     for(int i=1;i<=n;i++)scanf("%d%d%d%d",&X[i],&Y[i],&C[i],&D[i]);
49     for(int i=1,x,y;i<=m;i++){
50         scanf("%d%d",&x,&y);
51         d[x]++,d[y]++; 
52         Y[x]++,Y[y]++;
53         adde(0,i,1,0);
54         adde(i,m+x,1,0);
55         adde(i,m+y,1,0);
56     }
57     int ans=0;
58     for(int i=1,t;i<=n;i++){
59         ans+=(a[i]=cal(i));
60         if(!d[i])continue;
61         d[i]--;X[i]++,Y[i]--;
62         t=a[i],a[i]=cal(i); 
63         adde(m+i,n+m+1,1,a[i]-t);
64     }
65     ans += EK();
66     printf("%d
",ans);
67     return 0;
68 }
69 
70 
71 
72 
73 
74 
75 
76 
77 
78 
79 //考虑所有球队一开始都是输的；
80 //可以算出由输到胜的代价；
81 //用费用流去分配胜利场数即可；
82 //由于胜场增大增长率变大，所以是合法的； 
83 //害怕T所以用了动态加边； 
84 //20181213
85 
86 
87 
88 
89 
90 
91 
92 
93

View Code

bzoj2668[cqoi2012]交换棋子

题解：思考了很久才发现可以只看一个棋子，比如黑棋，把白旗看成无棋子，直接在限制内把黑棋移动到指定位置即可；

如果限制只每个格子经过多少次是很好做的（出入拆点建图跑费用流），但是题目限制交换次数；对于一条棋盘上路径的起点和终点，交换次数被用了一次，路径中的点被用了两次，这样对所有有黑棋的格子限制++再整体除以2变成了好做的问题；（其实个人认为这个题的最优路径不会相交不知对不对？）

  1 #include<bits/stdc++.h>
  2 #define inf 0x3f3f3f3f
  3 using namespace std;
  4 const int N=810,M=9010;
  5 int n,m,o,hd[N],vis[N],dis[N],T,mp[21][21],L[21][21],R[21][21],num1,num2;
  6 struct Edge{int u,v,nt,f,w;}E[M<<1];
  7 int dx[8]={0,0,1,-1,1,1,-1,-1};
  8 int dy[8]={1,-1,0,0,1,-1,1,-1};
  9 void adde(int u,int v,int f,int w){
 10     E[o]=(Edge){u,v,hd[u],f,w};hd[u]=o++;
 11     E[o]=(Edge){v,u,hd[v],0,-w};hd[v]=o++; 
 12 }
 13 queue<int>q;
 14 bool spfa(){
 15     memset(vis,0,sizeof(vis)); 
 16     memset(dis,0x3f,sizeof(dis));
 17     dis[T]=0;vis[T]=1;q.push(T);
 18     while(!q.empty()){
 19         int u=q.front();q.pop();
 20         vis[u]=0;
 21         for(int i=hd[u];~i;i=E[i].nt)if(E[i^1].f){
 22             int v=E[i].v;
 23             if(dis[v]>dis[u]+E[i^1].w){
 24                 dis[v]=dis[u]+E[i^1].w;
 25                 if(!vis[v])vis[v]=1,q.push(v);
 26             }
 27         } 
 28     }
 29     return dis[0]!=inf;
 30 }
 31 int dfs(int u,int F){
 32     vis[u]=1;
 33     if(u==T||!F)return F;
 34     int flow=0,f;
 35     for(int i=hd[u];~i;i=E[i].nt){
 36         int v=E[i].v;
 37         if(!vis[v]&&E[i].f&&dis[v]==dis[u]-E[i].w&&(f=dfs(v,min(F,E[i].f)))){
 38             flow+=f,F-=f;
 39             E[i].f-=f,E[i^1].f+=f;
 40             if(!F)break; 
 41         }
 42     }
 43     return flow;
 44 }
 45 int zkw(){
 46     int cost=0,f,flow=0;
 47     while(spfa()){
 48         do{
 49             memset(vis,0,sizeof(vis));
 50             f=dfs(0,inf);
 51             flow+=f;
 52             cost+=dis[0]*f;
 53         }while(vis[T]);
 54     }
 55     return flow==num1?cost:-1;
 56 }
 57 int main(){
 58     freopen("bzoj2668.in","r",stdin);
 59     freopen("bzoj2668.out","w",stdout);
 60     scanf("%d%d",&n,&m);
 61     T=n*m*2+1;
 62     memset(hd,-1,sizeof(hd));
 63     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
 64         L[i][j]=((i-1)*m+j)*2-1;
 65         R[i][j]=L[i][j]+1; 
 66     }
 67     for(int i=1;i<=n;i++){
 68         char s[22];scanf("%s",s+1);
 69         for(int j=1;j<=m;j++)if(s[j]-'0')adde(0,L[i][j],1,0),num1++,mp[i][j]++;
 70     }
 71     for(int i=1;i<=n;i++){
 72         char s[22];scanf("%s",s+1);
 73         for(int j=1;j<=m;j++)if(s[j]-'0')adde(R[i][j],T,1,0),num2++,mp[i][j]++;
 74     }
 75     if(num1!=num2){puts("-1");return 0;}
 76     for(int i=1;i<=n;i++){
 77         char s[22];scanf("%s",s+1);
 78         for(int j=1;j<=m;j++){
 79             mp[i][j]+=s[j]-'0';mp[i][j]>>=1;
 80             adde(L[i][j],R[i][j],mp[i][j],0);
 81             for(int k=0;k<8;k++){
 82                 int nx=i+dx[k],ny=j+dy[k];
 83                 if(nx<0||nx>n||ny<0||ny>m)continue;
 84                 adde(R[i][j],L[nx][ny],inf,1);
 85             }
 86         }
 87     }
 88     int ans = zkw();
 89     printf("%d
",ans);
 90     return 0;
 91 }
 92 
 93 
 94 
 95 
 96 
 97 
 98 
 99 
100 
101 
102 
103 
104 
105 
106 
107 
108 //细节各种出锅；
109 //和只有黑棋没有什么区别；
110 //意思是找多条路径把黑棋移动到指定位置集合；
111 //应该路径不会相交；
112 //那么直接出入度拆点，限制一下经过的次数即可；
113 //注意这题限制交换次数，所以路径的端点M++，再整体除以2即为实际的M值
114 //注意zkw的vis用法，注意空间不要开炸； 
115 //20181213
116 
117  
118 
119 
120  
121 
122 
123 
124

View Code

bzoj2864战火星空

题解：网上都说网络流部分比较简单，但是我就是没有撕烤出粗来

先读清楚题之后发现可以预处理出第i 个boss可以被飞机j打到的时间[sij,tij]，排序之后就有了很多个时间点t[k]我们把把boss j在时间段k看成点bkj ，飞机看成ai , 建图就是：对每架飞机<S,ai,Ei> ，每个时间段的每个飞机可以打到的目标 <ai,bkj,inf> ，boss每秒只能被一架飞机打到<bkj,T , tk+1 – tk >，由于NM只有20 dinic已经可以过了；

算几预处理的话先求垂足及飞到这个点的时间t0，再用勾股定理求长度d再考虑dt = d/v，[t0-dt,t0+dt]和飞机飞行时间取交即可，精度似乎没什么问题；

感觉可能会比较耐调，。。。。。。。。。

  1 #include<bits/stdc++.h>
  2 #define inf 1e18
  3 #define ld long double 
  4 #define eps 1e-9
  5 using namespace std;
  6 const int N=400010;
  7 struct point{
  8     ld x,y;
  9     point(ld _x=0,ld _y=0):x(_x),y(_y){};
 10     point operator +(const point&A){return point(x+A.x,y+A.y);}
 11     point operator -(const point&A){return point(x-A.x,y-A.y);}
 12     point operator *(const ld&A){return point(x*A,y*A);}
 13     ld operator ^(const point&A){return x*A.y-y*A.x;}
 14     ld operator *(const point&A){return x*A.x+y*A.y;}
 15 }A[21];
 16 struct line{point s,t;ld v,r,e;}B[21]; 
 17 int T,n,m,tot,o,hd[N],cur[N],vis[N],dis[N];
 18 ld s[21][21],t[21][21],sub[N];
 19 struct Edge{int v,nt; ld f;}E[N<<1];
 20 queue<int>q; 
 21 int dcmp(ld x){return fabs(x)<eps?0:x<0?-1:1;}
 22 point cross(point P,point v,point Q,point w){
 23     point u=P-Q;
 24     ld tmp=(w^u)/(v^w); 
 25     return P+v*tmp;
 26 }
 27 void cal(int i,int j){
 28     point P,Q,C,v,w; ld d,dt,t0,t1,t2,tl,tr;
 29     P=A[i];Q=B[j].s;
 30     w=B[j].t-B[j].s;
 31     v=point(-w.y,w.x); 
 32     C=cross(P,v,Q,w);
 33     v=C-P;
 34     d=(B[j].r*B[j].r)-(v*v);
 35     if(dcmp(d)<0)return;
 36     d=sqrt(d);
 37     dt=d/B[j].v;
 38     tl=0;tr=sqrt(w*w)/B[j].v;
 39     v=C-Q;
 40     if(dcmp(v.x*w.x)>0)t0=sqrt(v*v)/B[j].v;
 41     else t0=-sqrt(v*v)/B[j].v;
 42     t1=t0-dt,t2=t0+dt;
 43     s[i][j]=max(t1,tl);
 44     t[i][j]=min(t2,tr);
 45     if(dcmp(s[i][j]-t[i][j])<0){
 46         sub[++tot]=s[i][j];
 47         sub[++tot]=t[i][j];
 48     }
 49 }
 50 void adde(int u,int v,ld f){
 51 //    printf("%d %d %Lf
",u,v,f);
 52     E[o]=(Edge){v,hd[u],f};hd[u]=o++;
 53     E[o]=(Edge){u,hd[v],0};hd[v]=o++;
 54 } 
 55 bool in(ld s1,ld t1,ld s2,ld t2){return dcmp(s1-s2)<=0&&dcmp(t1-t2)>=0;}
 56 bool bfs(){
 57     for(int i=0;i<=T;i++)vis[i]=dis[i]=0;
 58     vis[0]=dis[0]=1;q.push(0);
 59     while(!q.empty()){
 60         int u=q.front();q.pop();
 61         for(int i=hd[u],v;~i;i=E[i].nt)if(dcmp(E[i].f)>0){
 62             if(!vis[v=E[i].v])vis[v]=1,q.push(v),dis[v]=dis[u]+1;
 63         } 
 64     }
 65     return vis[T];
 66 }
 67 ld dfs(int u,ld F){
 68     if(u==T||!dcmp(F))return F;
 69     ld flow=0,f;
 70     for(int i=cur[u];~i;i=E[i].nt){
 71         int v=E[cur[u]=i].v;
 72         if(dis[v]==dis[u]+1&&dcmp(f=dfs(v,min(F,E[i].f)))>0){
 73             flow+=f,F-=f;
 74             E[i].f-=f,E[i^1].f+=f;
 75             if(!dcmp(F))break;
 76         }
 77     }
 78     return flow;
 79 }
 80 ld dinic(){
 81     ld flow=0;
 82     while(bfs()){
 83         for(int i=0;i<=T;i++)cur[i]=hd[i];
 84         flow+=dfs(0,inf);
 85     }
 86     return flow;
 87 }
 88 int main(){
 89     freopen("bzoj2864.in","r",stdin);
 90     freopen("bzoj2864.out","w",stdout);
 91     memset(hd,-1,sizeof(hd));
 92     scanf("%d%d",&n,&m);
 93     for(int i=1;i<=n;i++)scanf("%Lf%Lf",&A[i].x,&A[i].y);
 94     for(int i=1;i<=m;i++){
 95         scanf("%Lf%Lf%Lf%Lf",&B[i].s.x,&B[i].s.y,&B[i].t.x,&B[i].t.y);
 96         scanf("%Lf%Lf%Lf",&B[i].v,&B[i].r,&B[i].e);
 97     }
 98     for(int i=1;i<=n;i++)
 99     for(int j=1;j<=m;j++){
100         cal(i,j);
101     }
102     sort(sub+1,sub+tot+1);
103     if(tot)tot--;T=tot*n+m+1;
104     for(int i=1;i<=m;i++)adde(0,i,B[i].e);
105     for(int i=1;i<=tot;i++)
106     for(int j=1;j<=n;j++){
107         adde((i-1)*n+j+m,T,sub[i+1]-sub[i]);
108     }
109     /*
110     for(int i=1;i<=tot;i++)printf("%.6Lf ",sub[i]);
111     puts("");
112     */
113     /*
114     for(int i=1;i<=n;i++)
115     for(int j=1;j<=m;j++){
116         printf("%.6Lf %.6Lf %6Lf
",s[i][j],t[i][j],t[i][j]-s[i][j]);
117     }*/
118     for(int i=1;i<=n;i++)
119     for(int j=1;j<=m;j++)
120     for(int k=1;k<=tot;k++)if(in(s[i][j],t[i][j],sub[k],sub[k+1])){
121         ld tmp=t[i][j]-s[i][j]; 
122         if(dcmp(tmp)>0)adde(j,(k-1)*n+m+i,inf);
123     }
124     ld ans = dinic();
125     printf("%.6Lf
",ans);
126     return 0;
127 }
128 
129 
130 
131 
132 
133 
134 
135 //这个题其实比较容易，但是前前后后搞了很久；
136 //算几预处理，得到每个飞机攻击每个boss的时间 
137 //网络流部分，题目中有条件：每个boss每个时间只能被一个飞机攻击，每个飞机有能量；
138 //这样把boss拆点即可；
139 //主要是没理解清楚题；
140 //20181216
141 
142 
143  
144 
145 
146 
147

View Code