fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct Network_sap{
  9.     #define Max_V 100000                 //最大点数
  10.     #define Max_E 1000000             //最大边数
  11.     int e,vs,vt;
  12.     struct edge{int x,y,c;edge *next,*op;}*ls[Max_V],*fa[Max_V],*cur[Max_V],g[Max_E];
  13.     int d[Max_V],num[Max_V];
  14.     #undef Max_V
  15.     #undef Max_E
  16.     void init(){e=0; memset(ls,0,sizeof(ls));}
  17.     void clear(){for (int i=0;i<e;i++) ls[g[i].x]=NULL; e=0;}
  18.     void push_back(int l,int r){    //把区间内反向弧的容量推回正向弧，清空流量
  19.         for (int i=l;i<=r;i++)
  20.           if (i&1){
  21.               g[i].op->c+=g[i].c;
  22.               g[i].c=0;
  23.           }
  24.     }
  25.     void refresh(int r){      //只留下前r条边
  26.         clear();
  27.         push_back(0,r-1);
  28.         for (int i=0;i<r;i++){
  29.           g[i].next=ls[g[i].x];
  30.           ls[g[i].x]=&g[i];
  31.         }
  32.         e=r;
  33.     }
  34.     void addedge(int x,int y,int c){
  35.         g[e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
  36.         e++;
  37.         g[e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
  38.         e++;
  39. //无向图加双边
  40.  /*
  41.         swap(x,y);
  42.         g[e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
  43.         e++;
  44.         g[e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
  45.         e++;
  46.  */
  47.     }
  48.     #define INF 0x7FFFFFFF
  49.     int sap(int n){     //注意是从1到n这个范围有点
  50.         int ret=0,i,nf;
  51.         for (i=1;i<=n;i++) d[i]=0,num[i]=0,cur[i]=ls[i];
  52.         for (i=vs,num[0]=n;d[vs]<n;){
  53.             edge *&t=cur[i];
  54.             while (t && !(t->c && d[t->y]+1==d[i])) t=t->next;
  55.             if (t){
  56.                 fa[t->y]=t;
  57.                 i=t->y;
  58.                 if (i==vt){
  59.                     for (nf=INF;i!=vs;i=fa[i]->x) if (fa[i]->c<nf) nf=fa[i]->c;
  60.                     for (i=vt  ;i!=vs;i=fa[i]->x) {fa[i]->c-=nf; fa[i]->op->c+=nf;}
  61.                     ret+=nf;
  62.                 }
  63.             }
  64.             else{
  65.                 if (--num[d[i]]==0) return ret;   // gap
  66.                 d[i]=n;
  67.                 for (t=ls[i];t;t=t->next)
  68.                   if (t->c && d[t->y]+1<d[i]) d[i]=d[t->y]+1;
  69.                 num[d[i]]++;
  70.                 t=ls[i];
  71.                 if (i!=vs) i=fa[i]->x;
  72.             }
  73.         }
  74.         return ret;
  75.     }
  76.     #undef INF
  77. }Network;
  78.  
  79. int n,m,Sum;
  80. int Low[1000000];
  81.  
  82. void init(){
  83.     Network.clear();
  84.     Sum=0;
  85.     scanf("%d%d",&n,&m);
  86.     Network.vs=n+1;
  87.     Network.vt=n+2;
  88.     for (int x,y,lower,upper,i=1;i<=m;i++){
  89.         scanf("%d%d%d%d",&x,&y,&lower,&upper);
  90.         Network.addedge(n+1,y,lower);
  91.         Network.addedge(x,n+2,lower);
  92.         Network.addedge(x,y,upper-lower);
  93.         Sum+=lower;
  94.         Low[Network.e-1]=lower;
  95.     }
  96. }
  97.  
  98. void gao(){
  99.     int ret=Network.sap(n+2);
  100.     if (ret==Sum){
  101.         puts("YES");
  102.         for (int i=5;i<Network.e;i+=6)
  103.           printf("%d\n",Low[i]+Network.g[i].c);
  104.     }
  105.     else puts("NO");
  106. }
  107.  
  108. int main(){
  109. //    freopen("input.txt","r",stdin);
  110.     int Tc,i;
  111.     scanf("%d",&Tc);
  112.     Network.init();
  113.     for (i=1;i<=Tc;i++){
  114.         init();
  115.         gao();
  116.         if (i!=Tc) puts("");
  117.     }
  118. }
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘void init()’:
prog.cpp:85: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:89: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp: In function ‘int main()’:
prog.cpp:111: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
Standard output is empty
https://ideone.com/t3Z6A
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!