[关闭]
@shixinyi 2017-12-22T13:24:40.000000Z 字数 21029 阅读 5046

网络流专题

OI

例题

网络流24题 方格取数

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=30*30+10,maxm=maxn*4,INF=0x3f3f3f3f;
  10. int n,m,S,T,ans;
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow;
  22.     Node(){}
  23.     Node(int x,int y,int cap):x(x),y(y),cap(cap){}
  24. }node[2*maxm];
  26. int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z) {
  28.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int zz[maxn],dis[maxn];
  33. bool BFS() {
  34.     int s=1,t=0,x,y,z;
  35.     memset(dis,-1,sizeof(dis));
  36.     zz[++t]=S;dis[S]=0;
  37.     while(s<=t) {
  38.         x=zz[s];s++;
  39.         for(y=fir[x];y;y=nxt[y]) {
  40.             z=node[y].y;
  41.             if(dis[z]!=-1||node[y].flow>=node[y].cap) continue;
  42.             dis[z]=dis[x]+1;
  43.             zz[++t]=z;
  44.         }
  45.     }
  46.     return dis[T]!=-1;
  47. }
  49. int DFS(int pos,int maxf) {
  50.     if(pos==T||!maxf) return maxf;
  51.     int now,z,rs=0;
  52.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  53.         z=node[y].y;
  54.         if(dis[z]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  55.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  56.         node[y].flow+=now; node[y^1].flow-=now;
  57.         maxf-=now; rs+=now;
  58.     }
  59.     if(!rs) dis[pos]=-1;
  60.     return rs;
  61. }
  63. int Dinic() {
  64.     int rs=0;
  65.     while(BFS()) {
  66.         memcpy(cur,fir,sizeof(cur));
  67.         rs+=DFS(S,INF);
  68.     }
  69.     return rs;
  70. }
  72. int main() {
  73.     n=read(); m=read(); int x,p,pos;
  74.     S=n*m+1; T=S+1;
  75.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
  76.         ans+=(x=read()); p=(i+j)&1; pos=(i-1)*m+j;
  77.         if(!p) add(S,pos,x); 
  78.         else add(pos,T,x);
  79.         if(i>1&&!p) add(pos,pos-m,INF);
  80.         else if(i>1) add(pos-m,pos,INF);
  81.         if(j>1&&!p) add(pos,pos-1,INF);
  82.         else if(j>1) add(pos-1,pos,INF);
  83.     }
  84.     printf("%d",ans-Dinic());
  85.     return 0;
  86. }

网络流24题 最长递增子序列

题目有毒，注意关于ans=1的情况的特判

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=1000+10,maxm=maxn*maxn/4+maxn,INF=0x3f3f3f3f;
  10. int n,a[maxn],f[maxn],ans,S,T;
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow;
  22.     Node(){}
  23.     Node(int x,int y,int cap):x(x),y(y),cap(cap){}
  24. }node[2*maxm];
  26. int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z) {
  28.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int zz[maxn],dis[maxn];
  33. bool BFS() {
  34.     int s=1,t=0,x,y,z;
  35.     memset(dis,-1,sizeof(dis));
  36.     zz[++t]=S;dis[S]=0;
  37.     while(s<=t) {
  38.         x=zz[s];s++;
  39.         for(y=fir[x];y;y=nxt[y]) {
  40.             z=node[y].y;
  41.             if(dis[z]!=-1||node[y].flow>=node[y].cap) continue;
  42.             dis[z]=dis[x]+1;
  43.             zz[++t]=z;
  44.         }
  45.     }
  46.     return dis[T]!=-1;
  47. }
  49. int DFS(int pos,int maxf) {
  50.     if(pos==T||!maxf) return maxf;
  51.     int now,z,rs=0;
  52.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  53.         z=node[y].y;
  54.         if(dis[z]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  55.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  56.         node[y].flow+=now; node[y^1].flow-=now;
  57.         maxf-=now; rs+=now;
  58.     }
  59.     if(!rs) dis[pos]=-1;
  60.     return rs;
  61. }
  63. int Dinic() {
  64.     int rs=0;
  65.     while(BFS()) {
  66.         memcpy(cur,fir,sizeof(cur));
  67.         rs+=DFS(S,INF);
  68.     }
  69.     return rs;
  70. }
  72. int main() {
  73.     n=read(); int x;
  74.     S=2*n+1; T=S+1;
  75.     for(int i=1;i<=n;++i) {
  76.         a[i]=read(); f[i]=1;
  77.         for(int j=1;j<i;++j) if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1);
  78.         ans=max(f[i],ans);
  79.     }
  80.     if(ans==1) printf("1\n%d\n%d",n,n);
  81.     else {
  82.         printf("%d\n",ans);
  83.         for(int i=1;i<=n;++i) {
  84.             add(i,i+n,1);
  85.             if(f[i]==1) add(S,i,1);
  86.             else if(f[i]==ans) add(i+n,T,1);
  87.         }
  88.         for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[j]>=a[i]&&f[j]==f[i]+1) add(i+n,j,1);//
  89.         printf("%d\n",Dinic());
  90.         memset(fir,0,sizeof(fir)); e=1;
  91.         for(int i=1;i<=n;++i) {
  92.             x= i==1||i==n? INF:1;
  93.             add(i,i+n,x);
  94.             if(f[i]==1) add(S,i,i==1? x:1);
  95.             else if(f[i]==ans) add(i+n,T,i==n? x:1);
  96.         }
  97.         for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[j]>=a[i]&&f[j]==f[i]+1) add(i+n,j,1);//
  98.         printf("%d",Dinic());
  99.     }
  100.     return 0;
  101. }

网络流24题 最小路径覆盖

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=400+10,maxm=6010+maxn;
  10. int n,m,k,S,T,tot,ans,rb[maxn],rd[maxn];
  11. bool pl[maxn];int v[maxn];
  13. int aa;char cc;
  14. int read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. struct Node{
  22.     int x,y,cap,flow;
  23. }node[2*maxm];
  25. int cur[maxn];
  26. int fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z) {
  28.     node[++e].x=x;node[e].y=y;node[e].cap=z; nxt[e]=fir[x];fir[x]=e;
  29.     node[++e].x=y;node[e].y=x;node[e].cap=0; nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int zz[maxn],dis[maxn],s=1,t=0;
  33. bool BFS() {
  34.     memset(dis,-1,sizeof(dis));
  35.     dis[S]=0; s=1,t=0;zz[++t]=S;
  36.     int x,y;
  37.     while(s<=t) {
  38.         x=zz[s];s++;
  39.         for(y=fir[x];y;y=nxt[y]) {
  40.             if(node[y].flow>=node[y].cap||dis[node[y].y]!=-1) continue;
  41.             dis[node[y].y]=dis[x]+1;
  42.             zz[++t]=node[y].y;
  43.         }
  44.     }
  45.     return dis[T]!=-1;
  46. }
  48. int DFS(int pos,int maxf) {
  49.     if(pos==T||!maxf) return maxf;
  50.     int rs=0,now;
  51.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  52.         if(node[y].flow>=node[y].cap||dis[node[y].y]!=dis[node[y].x]+1) continue;
  53.         now=DFS(node[y].y,min(maxf,node[y].cap-node[y].flow));
  54.         node[y].flow+=now;
  55.         node[y^1].flow-=now;
  56.         rs+=now;
  57.         maxf-=now;
  58.     }
  59.     if(!rs) dis[pos]=-1;
  60.     return rs;
  61. }
  63. int Dinic() {
  64.     int rs=0;
  65.     while(BFS()) {
  66.         memcpy(cur,fir,sizeof(fir));
  67.         rs+=DFS(S,0x3f3f3f3f);
  68.     }
  69.     return rs;
  70. }
  72. int main() {
  73.     n=read();m=read();tot=n;
  74.     int x,y; S=2*n+1;T=S+1;
  75.     for(int i=1;i<=n;++i) add(S,i,1),add(i+n,T,1);
  76.     for(int i=1;i<=m;++i) {
  77.         x=read();y=read();
  78.         add(x,y+n,1);
  79.     }
  80.     ans=tot-Dinic();
  81.     for(int i=2;i<=e;++i) {
  82.         if(node[i].x<=n&&node[i].flow==1) {
  83.             rb[node[i].x]=node[i].y-n;
  84.             rd[node[i].y-n]=1;
  85.         }
  86.     }
  87.     for(int i=1;i<=n;++i) if(!rd[i]){
  88.         x=i;printf("%d",i);
  89.         while(rb[x]) printf(" %d",x=rb[x]);
  90.         printf("\n");
  91.     }
  92.     printf("%d",ans);
  93.     return 0;
  94. }

网络流24题 魔术球

=> 

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=1570*2+10,maxm=maxn*maxn,INF=0x3f3f3f3f;
  10. int S,T,n,rb[maxn],rd[maxn];
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow;
  22.     Node(){}
  23.     Node(int x,int y,int cap):x(x),y(y),cap(cap){}
  24. }node[2*maxm];
  26. int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z) {
  28.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int zz[maxn],dis[maxn];
  33. bool BFS() {
  34.     int s=1,t=0,x,y,z;
  35.     memset(dis,-1,sizeof(dis));
  36.     zz[++t]=S;dis[S]=0;
  37.     while(s<=t) {
  38.         x=zz[s];s++;
  39.         for(y=fir[x];y;y=nxt[y]) {
  40.             z=node[y].y;
  41.             if(dis[z]!=-1||node[y].flow>=node[y].cap) continue;
  42.             dis[z]=dis[x]+1;
  43.             zz[++t]=z;
  44.         }
  45.     }
  46.     return dis[T]!=-1;
  47. }
  49. int DFS(int pos,int maxf) {
  50.     if(pos==T||!maxf) return maxf;
  51.     int now,z,rs=0;
  52.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  53.         z=node[y].y;
  54.         if(dis[z]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  55.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  56.         node[y].flow+=now; node[y^1].flow-=now;
  57.         maxf-=now; rs+=now;
  58.     }
  59.     if(!rs) dis[pos]=-1;
  60.     return rs;
  61. }
  63. int Dinic() {
  64.     int rs=0;
  65.     while(BFS()) {
  66.         memcpy(cur,fir,sizeof(cur));
  67.         rs+=DFS(S,INF);
  68.     }
  69.     return rs;
  70. }
  72. bool ok(int x) {
  73.     int xx=sqrt(x);
  74.     return xx*xx==x;
  75. } 
  77. bool check(int x) {
  78.     S=2*x+1;T=S+1; e=1;
  79.     memset(fir,0,sizeof(fir));
  80.     for(int i=1;i<=x;++i) for(int j=i+1;j<=x+1;++j) 
  81.         if(ok(i+j)) add(i,j+x,1);
  82.     for(int i=1;i<=x;++i) add(S,i,1),add(i+x,T,1);
  83.     return x-Dinic()<=n;
  84. }
  86. int main() {
  87.     n=read();int l=n,r=1570,mid,x;
  88.     while(l<r-1) {
  89.         mid=(l+r)>>1;
  90.         if(check(mid)) l=mid;
  91.         else r=mid;
  92.     }
  93.     printf("%d\n",l);check(l);
  94.     for(int i=2;i<=e;++i) {
  95.         if(node[i].x<=l&&node[i].flow==1) {
  96.             rb[node[i].x]=node[i].y-l;
  97.             rd[node[i].y-l]=1;
  98.         }
  99.     }
  100.     for(int i=1;i<=l;++i) if(!rd[i]){
  101.         x=i;printf("%d",i);
  102.         while(rb[x]) printf(" %d",x=rb[x]);
  103.         printf("\n");
  104.     }
  105.     return 0;
  106. }

网络流24题 餐巾计划

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=2000+10,maxm=4*maxn,INF=0x3f3f3f3f;
  10. int n,P,M,F,N,R,S,T;
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow,w;
  22.     Node(){}
  23.     Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){}
  24. }node[2*maxm];
  26. int fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z,int w) {
  28.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int from[maxn],zz[maxn],dis[maxn];
  33. bool vis[maxn];
  34. bool spfa() {
  35.     int s=1,t=0,x,y,z;
  36.     memset(dis,0x3f3f3f3f,sizeof(dis));
  37.     memset(zz,0,sizeof(zz));
  38.     zz[++t]=S;dis[S]=0;vis[S]=1;
  39.     while(s<=t) {
  40.         x=zz[s%maxn];s++;vis[x]=0;
  41.         for(y=fir[x];y;y=nxt[y]) {
  42.             if(node[y].flow>=node[y].cap||dis[z=node[y].y]<=dis[x]+node[y].w) continue;
  43.             dis[z]=dis[x]+node[y].w; from[z]=y;
  44.             if(!vis[z]) {
  45.                 vis[z]=1;t++;
  46.                 zz[t%maxn]=z;
  47.             }
  48.         }
  49.     }
  50.     return dis[T]!=INF;
  51. }
  53. int MCMF() {
  54.     int rs=0,now;
  55.     while(spfa()) {
  56.         now=INF;
  57.         for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
  58.         for(int i=T;i!=S;i=node[from[i]].x) {
  59.             node[from[i]].flow+=now;
  60.             node[from[i]^1].flow-=now;
  61.             rs+=node[from[i]].w*now;
  62.         }
  63.     }
  64.     return rs;
  65. }
  67. int main() {
  68.     n=read(); S=2*n+1;T=S+1; int x;
  69.     P=read();M=read();F=read();N=read();R=read();
  70.     for(int i=1;i<=n;++i) {
  71.         add(S,i+n,INF,P);
  72.         if(i+1<=n) add(i,i+1,INF,0);
  73.         if(i+M<=n) add(i,i+M+n,INF,F);
  74.         if(i+N<=n) add(i,i+N+n,INF,R); 
  75.     }
  76.     for(int i=1;i<=n;++i) {
  77.         x=read();
  78.         add(S,i,x,0);
  79.         add(i+n,T,x,0);
  80.     }
  81.     printf("%d",MCMF());
  82.     return 0;
  83. }

网络流24题 太空飞行计划

loj的数据有毒，注意输入方式，特别是不要用读入优化，否则可能WA和RE

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const int maxn=100+10,maxm=maxn*maxn,INF=0x3f3f3f3f;
  11. int n,m,ans,S,T;
  12. bool usd[maxn];
  13. char cc;
  15. struct Node{
  16.     int x,y,cap,flow;
  17.     Node(){}
  18.     Node(int x,int y,int cap):x(x),y(y),cap(cap){}
  19. }node[2*maxm];
  21. int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
  22. void add(int x,int y,int z) {
  23.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  24.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  25. }
  27. int zz[maxn],dis[maxn];
  28. bool BFS() {
  29.     int s=1,t=0,x,y,z;
  30.     memset(dis,-1,sizeof(dis));
  31.     zz[++t]=S;dis[S]=0;
  32.     while(s<=t) {
  33.         x=zz[s];s++;
  34.         for(y=fir[x];y;y=nxt[y]) {
  35.             z=node[y].y;
  36.             if(dis[z]!=-1||node[y].flow>=node[y].cap) continue;
  37.             dis[z]=dis[x]+1;
  38.             zz[++t]=z;
  39.         }
  40.     }
  41.     return dis[T]!=-1;
  42. }
  44. int DFS(int pos,int maxf) {
  45.     if(pos==T||!maxf) return maxf;
  46.     int now,z,rs=0;
  47.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  48.         z=node[y].y;
  49.         if(dis[z]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  50.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  51.         node[y].flow+=now; node[y^1].flow-=now;
  52.         maxf-=now; rs+=now;
  53.     }
  54.     if(!rs) dis[pos]=-1;
  55.     return rs;
  56. }
  58. int Dinic() {
  59.     int rs=0;
  60.     while(BFS()) {
  61.         memcpy(cur,fir,sizeof(cur));
  62.         rs+=DFS(S,INF);
  63.     }
  64.     return rs;
  65. }
  67. int main() {
  68.     scanf("%d%d",&n,&m);
  69.     S=n+m+1; T=S+1; int x;
  70.     for(int i=1;i<=n;++i) {
  71.         scanf("%d",&x); ans+=x;
  72.         add(S,i,x);
  73.         do{
  74.             cc=getchar();
  75.             if(cc=='\n'||cc=='\r'||cc==EOF) break;
  76.             scanf("%d",&x);add(i,n+x,INF);
  77.         }while(cc!='\n'&&cc!='\r'&&cc!=EOF);
  78.     }
  79.     for(int i=1;i<=m;++i) scanf("%d",&x),add(i+n,T,x);
  80.     ans-=Dinic();
  81.     for(int i=1;i<=n;++i) if(~dis[i]) {
  82.         printf("%d ",i);
  83.         for(int y=fir[i];y;y=nxt[y]) if(node[y].y<=n+m) usd[node[y].y-n]=1;
  84.     }
  85.     printf("\n");
  86.     for(int i=1;i<=m;++i) if(usd[i]) printf("%d ",i);
  87.     printf("\n%d",ans);
  88.     return 0;
  89. }

网络流24题 最长k可重区间集

题面有毒，他区间长度的计算方式是这样的： 

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=1000+10,maxm=2*maxn,INF=0x3f3f3f3f;
  10. int n,k,S,T,p[maxn],tot;
  12. struct Li{
  13.     int l,r;
  14. }line[maxn];
  16. int aa;char cc;
  17. int read() {
  18.     aa=0;cc=getchar();
  19.     while(cc<'0'||cc>'9') cc=getchar();
  20.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  21.     return aa;
  22. }
  23. struct Node{
  24.     int x,y,cap,flow,w;
  25.     Node(){}
  26.     Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){}
  27. }node[2*maxm];
  28. int fir[maxn],nxt[2*maxm],e=1;
  29. void add(int x,int y,int z,int w) {
  30.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
  31.     node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;
  32. //    printf("add: %d->%d z:%d w:%d\n",x,y,z,w);
  33. }
  34. int from[maxn],zz[maxn],dis[maxn];
  35. bool vis[maxn];
  36. bool spfa() {
  37.     int s=1,t=0,x,y,z;
  38.     memset(dis,-1,sizeof(dis));
  39.     memset(zz,0,sizeof(zz));
  40.     zz[++t]=S;dis[S]=0;vis[S]=1;
  41.     while(s<=t) {
  42.         x=zz[s%maxn];s++;vis[x]=0;
  43.         for(y=fir[x];y;y=nxt[y]) {
  44.             if(node[y].flow>=node[y].cap||dis[z=node[y].y]>=dis[x]+node[y].w) continue;
  45.             dis[z]=dis[x]+node[y].w; from[z]=y;
  46.             if(!vis[z]) {
  47.                 vis[z]=1;t++;
  48.                 zz[t%maxn]=z;
  49.             }
  50.         }
  51.     }
  52.     return dis[T]!=-1;
  53. }
  54. int MCMF() {
  55.     int rs=0,now;
  56.     while(spfa()) {
  57.         now=INF;
  58.         for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
  59.         for(int i=T;i!=S;i=node[from[i]].x) {
  60.             node[from[i]].flow+=now;
  61.             node[from[i]^1].flow-=now;
  62.             rs+=node[from[i]].w*now;
  63.         }
  64.     }
  65.     return rs;
  66. }
  68. int ef(int x) {
  69.     int l=1,r=tot,mid;
  70.     while(l<=r) {
  71.         mid=(l+r)>>1;
  72.         if(p[mid]==x) return mid;
  73.         if(p[mid]<x) l=mid+1;
  74.         else r=mid-1;
  75.     }
  76. }
  78. int main() {
  79.     n=read(); k=read();
  80.     for(int i=1;i<=n;++i) {
  81.         p[++tot]=line[i].l=read();
  82.         p[++tot]=line[i].r=read();
  83.         if(line[i].l>line[i].r) swap(line[i].l,line[i].r);
  84.     }
  85.     sort(p+1,p+tot+1);
  86.     tot=unique(p+1,p+tot+1)-(p+1);
  87.     for(int i=1;i<=n;++i) add(ef(line[i].l),ef(line[i].r),1,line[i].r-line[i].l);
  88.     for(int i=1;i<tot;++i) add(i,i+1,k,0);
  89.     S=tot+1; T=S+1;
  90.     add(S,1,k,0); add(tot,T,k,0);
  91.     printf("%d",MCMF());
  92.     return 0;
  93. }

bzoj3442 学习小组

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=200+10,maxm=20000+10,INF=0x3f3f3f3f;
  10. int n,m,k,C[maxn],F[maxn],S,T;
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow,w;
  22.     Node(){}
  23.     Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){flow=0;}
  24. }node[2*maxm];
  26. int fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z,int w) {
  28.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int from[maxn],zz[maxn],dis[maxn];
  33. bool vis[maxn];
  34. bool spfa() {
  35.     int s=1,t=0,x,y,z;
  36.     memset(dis,0x3f3f3f3f,sizeof(dis));
  37.     memset(zz,0,sizeof(zz));
  38.     zz[++t]=S;dis[S]=0;vis[S]=1;
  39.     while(s<=t) {
  40.         x=zz[s%maxn];s++;vis[x]=0;
  41.         for(y=fir[x];y;y=nxt[y]) {
  42.             if(node[y].flow>=node[y].cap||dis[z=node[y].y]<=dis[x]+node[y].w) continue;
  43.             dis[z]=dis[x]+node[y].w; from[z]=y;
  44.             if(!vis[z]) {
  45.                 vis[z]=1;t++;
  46.                 zz[t%maxn]=z;
  47.             }
  48.         }
  49.     }
  50.     return dis[T]!=INF;
  51. }
  53. int MCMF() {
  54.     int rs=0,now;
  55.     while(spfa()) {
  56.         now=INF;
  57.         for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
  58.         for(int i=T;i!=S;i=node[from[i]].x) {
  59.             node[from[i]].flow+=now;
  60.             node[from[i]^1].flow-=now;
  61.             rs+=node[from[i]].w*now;
  62.         }
  63.     }
  64.     return rs;
  65. }
  67. int main() {
  68.     n=read(); m=read(); k=read();
  69.     S=n+m+1;T=S+1; int x;
  70.     for(int i=1;i<=n;++i) {
  71.         add(S,i,k,0);
  72.         add(i,T,k-1,0);
  73.     }
  74.     for(int i=1;i<=m;++i) C[i]=read();
  75.     for(int i=1;i<=m;++i) F[i]=read();
  76.     for(int i=1;i<=m;++i) 
  77.         for(int j=1;j<=n;++j) 
  78.             add(n+i,T,1,(2*j-1)*C[i]-F[i]);
  79.     for(int i=1;i<=n;++i)
  80.         for(int j=1;j<=m;++j) {
  81.             scanf("%1d",&x);
  82.             if(x) add(i,n+j,1,0);
  83.         }
  84.     printf("%d",MCMF());
  85.     return 0;
  86. }

bzoj1061 志愿者招募

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=1000+10,maxm=30*maxn,INF=0x3f3f3f3f;
  10. int n,m,S,T,p[maxn];
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow,w;
  22.     Node(){}
  23.     Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){flow=0;}
  24. }node[2*maxm];
  26. int fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z,int w) {
  28.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int from[maxn],zz[maxn],dis[maxn];
  33. bool vis[maxn];
  34. bool spfa() {
  35.     int s=1,t=0,x,y,z;
  36.     memset(dis,0x3f3f3f3f,sizeof(dis));
  37.     memset(zz,0,sizeof(zz));
  38.     zz[++t]=S;dis[S]=0;vis[S]=1;
  39.     while(s<=t) {
  40.         x=zz[s%maxn];s++;vis[x]=0;
  41.         for(y=fir[x];y;y=nxt[y]) {
  42.             if(node[y].flow>=node[y].cap||dis[z=node[y].y]<=dis[x]+node[y].w) continue;
  43.             dis[z]=dis[x]+node[y].w; from[z]=y;
  44.             if(!vis[z]) {
  45.                 vis[z]=1;t++;
  46.                 zz[t%maxn]=z;
  47.             }
  48.         }
  49.     }
  50.     return dis[T]!=INF;
  51. }
  53. int MCMF() {
  54.     int rs=0,now;
  55.     while(spfa()) {
  56.         now=INF;
  57.         for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
  58.         for(int i=T;i!=S;i=node[from[i]].x) {
  59.             node[from[i]].flow+=now;
  60.             node[from[i]^1].flow-=now;
  61.             rs+=node[from[i]].w*now;
  62.         }
  63.     }
  64.     return rs;
  65. }
  67. int main() {
  68.     n=read(); m=read();
  69.     S=n+2;T=S+1;
  70.     for(int i=1;i<=n;++i) p[i]=read();
  71.     for(int i=1;i<=n+1;++i) {
  72.         if(p[i-1]-p[i]>0) add(S,i,p[i-1]-p[i],0);
  73.         else add(i,T,p[i]-p[i-1],0);
  74.     }
  75.     int l,r,c;
  76.     for(int i=1;i<=m;++i) {
  77.         l=read(); r=read(); c=read();
  78.         add(r+1,l,INF,c);
  79.     }
  80.     for(int i=1;i<=n;++i) add(i,i+1,INF,0);
  81.     printf("%d",MCMF());
  82.     return 0;
  83. }

vijos1891 学姐的逛街计划

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=400+10,maxm=4*maxn,INF=0x3f3f3f3f;
  10. int n,k,S,T,c[2*maxn];
  12. int aa;char cc;
  13. int read() {
  14.     aa=0;cc=getchar();
  15.     while(cc<'0'||cc>'9') cc=getchar();
  16.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  17.     return aa;
  18. }
  20. struct Node{
  21.     int x,y,cap,flow,w;
  22.     Node(){}
  23.     Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){}
  24. }node[2*maxm];
  26. int fir[maxn],nxt[2*maxm],e=1;
  27. void add(int x,int y,int z,int w) {
  28.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
  29.     node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;
  30. }
  32. int from[maxn],zz[maxn],dis[maxn];
  33. bool vis[maxn];
  34. bool spfa() {
  35.     int s=1,t=0,x,y,z;
  36.     memset(dis,-1,sizeof(dis));
  37.     memset(zz,0,sizeof(zz));
  38.     zz[++t]=S;dis[S]=0;vis[S]=1;
  39.     while(s<=t) {
  40.         x=zz[s%maxn];s++;vis[x]=0;
  41.         for(y=fir[x];y;y=nxt[y]) {
  42.             if(node[y].flow>=node[y].cap||dis[z=node[y].y]>=dis[x]+node[y].w) continue;
  43.             dis[z]=dis[x]+node[y].w; from[z]=y;
  44.             if(!vis[z]) {
  45.                 vis[z]=1;t++;
  46.                 zz[t%maxn]=z;
  47.             }
  48.         }
  49.     }
  50.     return dis[T]!=-1;
  51. }
  53. int MCMF() {
  54.     int rs=0,now;
  55.     while(spfa()) {
  56.         now=INF;
  57.         for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
  58.         for(int i=T;i!=S;i=node[from[i]].x) {
  59.             node[from[i]].flow+=now;
  60.             node[from[i]^1].flow-=now;
  61.             rs+=node[from[i]].w*now;
  62.         }
  63.     }
  64.     return rs;
  65. }
  67. int main() {
  68.     n=read(); k=read();
  69.     S=2*n+2;T=S+1;
  70.     for(int i=1;i<=3*n;++i) c[i]=read();
  71.     for(int i=1;i<=n;++i) add(i,i+n,1,c[i+n]);
  72.     for(int i=1;i<2*n;++i) add(i,i+1,k,0);
  73.     for(int i=1;i<=n;++i) add(2*n+1,i,1,c[i]);
  74.     for(int i=n+1;i<=2*n;++i) add(i,T,1,c[i+n]);
  75.     add(S,2*n+1,k,0);
  76.     printf("%d",MCMF());
  77.     return 0;
  78. }

test 1212night A

题面有毒，汇点应该是n.

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. #define ll long long
  10. const ll maxn=200+10,maxm=1000+10,INF=1e9;
  11. ll n,m,S,T,ind[maxn];
  12. ll ans;
  14. ll aa;char cc;
  15. ll read() {
  16.     aa=0;cc=getchar();
  17.     while(cc<'0'||cc>'9') cc=getchar();
  18.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  19.     return aa;
  20. }
  22. struct Node{
  23.     int x,y;ll cap,flow,w;
  24.     Node(){}
  25.     Node(int x,int y,ll cap,ll w):x(x),y(y),cap(cap),w(w){flow=0;}
  26. }node[2*maxm];
  28. int fir[maxn],nxt[2*maxm],e=1;
  29. void add(int x,int y,ll z,ll w) {
  30. //  printf("add:%d -> %d cap:%lld w:%lld\n",x,y,z,w);
  31.     node[++e]=Node(x,y,z,w); nxt[e]=fir[x]; fir[x]=e;
  32.     node[++e]=Node(y,x,0,-w); nxt[e]=fir[y];fir[y]=e;
  33. }
  35. ll zz[maxn],dis[maxn],from[maxn];
  36. bool vis[maxn];
  37. bool spfa() {
  38.     for(int i=1;i<=n+2;++i) dis[i]=INF,from[i]=0;
  39.     int s=1,t=0,x,y,z,o;
  40.     dis[S]=0; zz[++t]=S;vis[S]=1;
  41.     while(s<=t) {
  42.         x=zz[s%maxn];s++; vis[x]=0;
  43.         for(y=fir[x];y;y=nxt[y]) {
  44.             z=node[y].y;
  45.             if(node[y].flow>=node[y].cap||dis[z]<=dis[x]+node[y].w) continue;
  46.             dis[z]=dis[x]+node[y].w;
  47.             from[z]=y;
  48.             if(!vis[z]) {
  49.                 vis[z]=1; t++;
  50.                 zz[t%maxn]=z;
  51.             }
  52.         }
  53.     }
  54.     return dis[T]<INF;
  55. }
  57. ll MCMF() {
  58.     ll rs=0,now;
  59.     while(spfa()) {
  60.         now=INF;
  61.         for(int x=T;x!=S;x=node[from[x]].x) now=min(now,node[from[x]].cap-node[from[x]].flow);
  62.         for(int x=T;x!=S;x=node[from[x]].x) {
  63.             rs+=now*node[from[x]].w;
  64.             node[from[x]].flow+=now;
  65.             node[from[x]^1].flow-=now;
  66.         }
  67.     }
  68.     return rs;
  69. }
  71. int main() {
  72.     n=read(); m=read();
  73.     int x,y,f,c; S=n+1;T=n+2;
  74.     for(int i=1;i<=m;++i) {
  75.         x=read(); y=read(); c=read(); f=read();
  76.         ind[y]+=f; ind[x]-=f;
  77.         if(f<=c) {
  78.             add(y,x,f,1);
  79.             if(f!=c) add(x,y,c-f,1);
  80.             add(x,y,INF,2);
  81.         }
  82.         else { 
  83.             ans+=f-c;
  84.             add(y,x,f-c,0);
  85.             add(y,x,c,1);
  86.             add(x,y,INF,2);
  87.         }
  88.     }
  89.     for(int i=1;i<=n;++i) {
  90.         if(ind[i]<0) add(i,T,-ind[i],0);
  91.         else if(ind[i]>0) add(S,i,ind[i],0);
  92.     }
  93.     add(n,1,INF,0);
  94.     ans+=MCMF();
  95.     printf("%lld",ans);
  96.     return 0;
  97. }

test 1213 T2 百步穿杨

数据第4、5个点有毒。

  1. //Serene
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<cstdio>
  7. #include<cmath>
  8. using namespace std;
  9. const int maxn=2e4+10,INF=0x3f3f3f3f;
  10. int n,m,S,T,ans;
  11. char c[57][57];
  13. int aa;char cc;
  14. int read() {
  15.     aa=0;cc=getchar();
  16.     while(cc<'0'||cc>'9') cc=getchar();
  17.     while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
  18.     return aa;
  19. }
  21. int is_ok(char x) {
  22.     if(x=='.') return 0;
  23.     if(x>='0'&&x<='9') return x-'0';
  24.     if(x=='A'||x=='V'||x=='<'||x=='>') return -1;
  25.     return -2;
  26. }
  28. struct Node{
  29.     int x,y,cap,flow;
  30.     Node(){}
  31.     Node(int x,int y,int cap):x(x),y(y),cap(cap){flow=0;}
  32. }node[6*maxn];
  34. int cur[maxn],fir[maxn],nxt[6*maxn],e=1;
  35. void add(int x,int y,int z) {
  36. //  printf("add:%d -> %d cap:%d\n",x,y,z);
  37.     node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e;
  38.     node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;
  39. }
  41. int get_id(int x,int y,int p) {
  42.     return (x-1)*m+y+p*n*m;
  43. }
  45. void init() {
  46.     int xx,yy,dx,dy,nowmax,num,p;
  47.     for(int i=0;i<=n+1;++i) c[i][0]=c[i][m+1]='#';
  48.     for(int i=0;i<=m+1;++i) c[0][i]=c[n+1][i]='#';
  49.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(is_ok(c[i][j])==-1){
  50.         switch(c[i][j]) {
  51.             case 'A':dx=-1;dy=0;p=1;break;
  52.             case 'V':dx=1;dy=0; p=1;break;
  53.             case '<':dx=0;dy=-1;p=0;break;
  54.             case '>':dx=0;dy=1; p=0;break;
  55.         }
  56.         xx=i+dx; yy=j+dy;
  57.         nowmax=0;
  58.         while((num=is_ok(c[xx][yy]))>=0) {
  59.             if(num>nowmax) nowmax=num;
  60.             xx+=dx; yy+=dy;
  61.         }
  62.         if(!nowmax) continue; ans+=nowmax;
  63.         xx=i; yy=j; num=0;
  64.         do{
  65.             if(!p) add(get_id(xx,yy,0),get_id(xx+dx,yy+dy,0),nowmax-num);
  66.             else add(get_id(xx+dx,yy+dy,1),get_id(xx,yy,1),nowmax-num);
  67.             xx+=dx; yy+=dy;
  68.         }while((num=is_ok(c[xx][yy]))!=nowmax);
  69.         if(!p) add(S,get_id(i,j,0),INF);
  70.         else add(get_id(i,j,1),T,INF);
  71.     }
  72.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) add(get_id(i,j,0),get_id(i,j,1),INF);
  73. }
  75. int dis[maxn],zz[maxn];
  76. bool BFS() {
  77.     memset(dis,-1,sizeof(dis));
  78.     int s=1,t=0,x,y,z;
  79.     zz[++t]=S; dis[S]=1;
  80.     while(s<=t) {
  81.         x=zz[s++];
  82.         for(y=fir[x];y;y=nxt[y]) {
  83.             if(dis[z=node[y].y]!=-1||node[y].flow>=node[y].cap) continue;
  84.             dis[z]=dis[x]+1;
  85.             zz[++t]=z;
  86.         }
  87.     }
  88.     return dis[T]!=-1;
  89. }
  91. int DFS(int pos,int maxf) {
  92.     if(pos==T||!maxf) return maxf;
  93.     int rs=0,now,z;
  94.     for(int &y=cur[pos];y&&maxf;y=nxt[y]) {
  95.         if(dis[z=node[y].y]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
  96.         now=DFS(z,min(maxf,node[y].cap-node[y].flow));
  97.         node[y].flow+=now; node[y^1].flow-=now;
  98.         rs+=now;maxf-=now;
  99.     }
  100.     if(!rs) dis[pos]=-1;
  101.     return rs;
  102. }
  104. int Dinic() {
  105.     int rs=0;
  106.     while(BFS()) {
  107.         memcpy(cur,fir,sizeof(fir));
  108.         rs+=DFS(S,INF);
  109.     }
  110.     return rs;
  111. }
  113. int main() {
  114.     freopen("archery.in","r",stdin);
  115.     freopen("archery.out","w",stdout);
  116.     n=read(); m=read();
  117.     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) do c[i][j]=getchar();while(is_ok(c[i][j])<-1);
  118.     S=2*n*m+1; T=S+1;
  119.     init();
  120.     ans-=Dinic();
  121.     printf("%d\n",ans);
  122.     return 0;
  123. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注