无源汇上下界可行流
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<set> 10 #include<bitset> 11 #include<vector> 12 #include<cstdlib> 13 #define QAQ int 14 #define TAT long long 15 #define OwO bool 16 #define ORZ double 17 #define F(i,j,n) for(QAQ i=j;i<=n;++i) 18 #define E(i,j,n) for(QAQ i=j;i>=n;--i) 19 #define MES(i,j) memset(i,j,sizeof(i)) 20 #define MEC(i,j) memcpy(i,j,sizeof(j)) 21 22 using namespace std; 23 const QAQ N=305,M=30000; 24 25 QAQ n,m,s,t; 26 struct Link{ 27 QAQ to,last,val,id; 28 }a[M]; 29 QAQ head[N],js=1; 30 QAQ dis[N],use[N],ans[M]; 31 QAQ low[M],flow[N]; 32 OwO vis[N]; 33 queue<QAQ> q; 34 35 void add(QAQ x,QAQ y,QAQ z,QAQ p){ 36 a[++js].to=y;a[js].id=p;a[js].val=z; 37 a[js].last=head[x];head[x]=js; 38 } 39 40 OwO bfs(){ 41 F(i,s,t) dis[i]=vis[i]=0; 42 dis[s]=vis[s]=1; 43 q.push(s); 44 while(!q.empty()){ 45 QAQ x=q.front();q.pop(); 46 for(QAQ i=head[x];i;i=a[i].last) if(a[i].val&&!vis[a[i].to]){ 47 vis[a[i].to]=1; 48 dis[a[i].to]=dis[x]+1; 49 q.push(a[i].to); 50 } 51 } 52 return vis[t]; 53 } 54 55 QAQ dfs(QAQ x,QAQ want){ 56 if(x==t||!want) return want; 57 QAQ f=0,ans=0; 58 for(QAQ i=use[x];i;i=a[i].last) if(dis[a[i].to]==dis[x]+1){ 59 f=dfs(a[i].to,min(a[i].val,want)); 60 if(!f) continue; 61 ans+=f; 62 want-=f; 63 a[i].val-=f; 64 a[i^1].val+=f; 65 if(!want) break; 66 use[x]=i; 67 } 68 if(!ans) dis[x]=-1; 69 return ans; 70 } 71 72 QAQ dinic(){ 73 QAQ ans=0; 74 while(bfs()){ 75 MEC(use,head); 76 ans+=dfs(s,1e9); 77 } 78 return ans; 79 } 80 81 QAQ main(){ 82 scanf("%d%d",&n,&m); 83 s=0;t=n+1; 84 F(i,1,m){ 85 QAQ u,v,w; 86 scanf("%d%d%d%d",&u,&v,&low[i],&w); 87 add(u,v,w-low[i],i); 88 add(v,u,0,i); 89 flow[v]+=low[i]; 90 flow[u]-=low[i]; 91 } 92 QAQ sum=0; 93 F(i,1,n) if(flow[i]<0){ 94 add(i,t,-flow[i],0); 95 add(t,i,0,0); 96 } 97 else { 98 sum+=flow[i]; 99 add(s,i,flow[i],0); 100 add(i,s,0,0); 101 } 102 if(dinic()==sum){ 103 printf("YES\n"); 104 F(x,1,n) for(QAQ i=head[x];i;i=a[i].last) if(a[i].id==0||i%2==0) continue; 105 else { 106 ans[a[i].id]=a[i].val+low[a[i].id]; 107 } 108 F(i,1,m) printf("%d\n",ans[i]); 109 } 110 else printf("NO\n"); 111 return 0; 112 } View Code有源汇有上下界最大流
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<set> 10 #include<bitset> 11 #include<vector> 12 #include<cstdlib> 13 #define QAQ int 14 #define TAT long long 15 #define OwO bool 16 #define ORZ double 17 #define F(i,j,n) for(QAQ i=j;i<=n;++i) 18 #define E(i,j,n) for(QAQ i=j;i>=n;--i) 19 #define MES(i,j) memset(i,j,sizeof(i)) 20 #define MEC(i,j) memcpy(i,j,sizeof(j)) 21 22 using namespace std; 23 const QAQ N=405,M=30000; 24 25 QAQ n,m,s,t,ss,tt; 26 struct Link{ 27 QAQ to,last,val,id; 28 }a[M]; 29 QAQ head[N],js=1; 30 QAQ dis[N],use[N],ans[M]; 31 QAQ low[M],flow[N]; 32 OwO vis[N]; 33 queue<QAQ> q; 34 35 void add(QAQ x,QAQ y,QAQ z,QAQ p){ 36 a[++js].to=y;a[js].id=p;a[js].val=z; 37 a[js].last=head[x];head[x]=js; 38 } 39 40 OwO bfs(){ 41 F(i,0,n+1) dis[i]=vis[i]=0; 42 dis[ss]=vis[ss]=1; 43 q.push(ss); 44 while(!q.empty()){ 45 QAQ x=q.front();q.pop(); 46 for(QAQ i=head[x];i;i=a[i].last) if(a[i].val&&!vis[a[i].to]){ 47 vis[a[i].to]=1; 48 dis[a[i].to]=dis[x]+1; 49 q.push(a[i].to); 50 } 51 } 52 return vis[tt]; 53 } 54 55 QAQ dfs(QAQ x,QAQ want){ 56 if(x==tt||!want) return want; 57 QAQ f=0,ans=0; 58 for(QAQ i=use[x];i;i=a[i].last) if(dis[a[i].to]==dis[x]+1){ 59 f=dfs(a[i].to,min(a[i].val,want)); 60 if(!f) continue; 61 ans+=f; 62 want-=f; 63 a[i].val-=f; 64 a[i^1].val+=f; 65 if(!want) break; 66 use[x]=i; 67 } 68 if(!ans) dis[x]=-1; 69 return ans; 70 } 71 72 QAQ dinic(){ 73 QAQ ans=0; 74 while(bfs()){ 75 MEC(use,head); 76 ans+=dfs(ss,1e9); 77 } 78 return ans; 79 } 80 81 QAQ main(){ 82 scanf("%d%d%d%d",&n,&m,&s,&t); 83 ss=0;tt=n+1; 84 F(i,1,m){ 85 QAQ u,v,w; 86 scanf("%d%d%d%d",&u,&v,&low[i],&w); 87 add(u,v,w-low[i],i); 88 add(v,u,0,i); 89 flow[v]+=low[i]; 90 flow[u]-=low[i]; 91 } 92 QAQ sum=0; 93 F(i,1,n) if(flow[i]<0){ 94 add(i,tt,-flow[i],0); 95 add(tt,i,0,0); 96 } 97 else { 98 sum+=flow[i]; 99 add(ss,i,flow[i],0); 100 add(i,ss,0,0); 101 } 102 add(t,s,1e9,0); 103 if(dinic()==sum){ 104 sum=a[head[t]^1].val; 105 F(i,2,js) if(!a[i].id) a[i].val=0; 106 head[ss]=head[tt]=0; 107 ss=s;tt=t; 108 printf("%d\n",sum+dinic()); 109 } 110 else printf("please go home to sleep\n"); 111 return 0; 112 } View Code有源汇有上下界最小流
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<set> 10 #include<bitset> 11 #include<vector> 12 #include<cstdlib> 13 #define QAQ int 14 #define TAT long long 15 #define OwO bool 16 #define ORZ double 17 #define F(i,j,n) for(QAQ i=j;i<=n;++i) 18 #define E(i,j,n) for(QAQ i=j;i>=n;--i) 19 #define MES(i,j) memset(i,j,sizeof(i)) 20 #define MEC(i,j) memcpy(i,j,sizeof(j)) 21 22 using namespace std; 23 const QAQ N=70000,M=2000000; 24 25 QAQ n,m,s,t,ss,tt; 26 struct Link{ 27 QAQ to,last,val,id; 28 }a[M]; 29 QAQ head[N],js=1; 30 QAQ dis[N],use[N],ans[M]; 31 QAQ low[M],flow[N]; 32 OwO vis[N]; 33 queue<QAQ> q; 34 35 inline void read(int &x){ 36 int f = 0, ch = 0; x = 0; 37 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1; 38 for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; 39 if(f) x = -x; 40 } 41 42 void add(QAQ x,QAQ y,QAQ z,QAQ p){ 43 a[++js].to=y;a[js].id=p;a[js].val=z; 44 a[js].last=head[x];head[x]=js; 45 } 46 47 OwO bfs(){ 48 F(i,0,n+1) dis[i]=vis[i]=0; 49 dis[ss]=vis[ss]=1; 50 q.push(ss); 51 while(!q.empty()){ 52 QAQ x=q.front();q.pop(); 53 for(QAQ i=head[x];i;i=a[i].last) if(a[i].val&&!vis[a[i].to]){ 54 vis[a[i].to]=1; 55 dis[a[i].to]=dis[x]+1; 56 q.push(a[i].to); 57 } 58 } 59 return vis[tt]; 60 } 61 62 QAQ dfs(QAQ x,QAQ want){ 63 if(x==tt||!want) return want; 64 QAQ f=0,ans=0; 65 for(QAQ i=use[x];i;i=a[i].last) if(dis[a[i].to]==dis[x]+1){ 66 f=dfs(a[i].to,min(a[i].val,want)); 67 if(!f) continue; 68 ans+=f; 69 want-=f; 70 a[i].val-=f; 71 a[i^1].val+=f; 72 if(!want) break; 73 use[x]=i; 74 } 75 if(!ans) dis[x]=-1; 76 return ans; 77 } 78 79 QAQ dinic(){ 80 QAQ ans=0; 81 while(bfs()){ 82 F(i,0,n+1) use[i]=head[i]; 83 ans+=dfs(ss,2e9); 84 } 85 return ans; 86 } 87 88 QAQ main(){ 89 // freopen("8.in","r",stdin); 90 read(n);read(m);read(s);read(t); 91 // scanf("%d%d%d%d",&n,&m,&s,&t); 92 ss=0;tt=n+1; 93 F(i,1,m){ 94 QAQ u,v,w; 95 read(u);read(v);read(low[i]);read(w); 96 // scanf("%d%d%d%d",&u,&v,&low[i],&w); 97 add(u,v,w-low[i],i); 98 add(v,u,0,i); 99 flow[v]+=low[i]; 100 flow[u]-=low[i]; 101 } 102 QAQ sum=0; 103 F(i,1,n) if(flow[i]<0){ 104 add(i,tt,-flow[i],0); 105 add(tt,i,0,0); 106 } 107 else { 108 sum+=flow[i]; 109 add(ss,i,flow[i],0); 110 add(i,ss,0,0); 111 } 112 add(t,s,2e9,0); 113 if(dinic()==sum){ 114 sum=a[head[t]^1].val; 115 F(i,2,js) if(!a[i].id) a[i].val=0; 116 head[ss]=head[tt]=0; 117 ss=t;tt=s; 118 printf("%d\n",sum-dinic()); 119 } 120 else printf("please go home to sleep\n"); 121 return 0; 122 } View Code有源汇上下界费用流([AHOI2014/JSOI2014]支线剧情)
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<set> 10 #include<bitset> 11 #include<sstream> 12 #include<cstdlib> 13 #define QAQ int 14 #define TAT long long 15 #define OwO bool 16 #define ORZ double 17 #define Ug unsigned 18 #define F(i,j,n) for(QAQ i=j;i<=n;++i) 19 #define E(i,j,n) for(QAQ i=j;i>=n;--i) 20 #define MES(i,j) memset(i,j,sizeof(i)) 21 #define MEC(i,j) memcpy(i,j,sizeof(j)) 22 23 using namespace std; 24 const QAQ N=505,M=5000000; 25 const QAQ oo=1e8; 26 27 QAQ n,m,s,t; 28 struct Link{ 29 QAQ to,last,rem,val,from; 30 }a[M]; 31 QAQ head[N],js=1,ans; 32 QAQ dis[N]; 33 OwO vis[N]; 34 queue<QAQ> q; 35 36 void add(QAQ x,QAQ y,QAQ z,QAQ w){ 37 a[++js].from=x;a[js].to=y; 38 a[js].rem=z;a[js].val=w; 39 a[js].last=head[x];head[x]=js; 40 } 41 42 void Insert(QAQ x,QAQ y,QAQ z,QAQ w){ 43 add(x,y,z,w);add(y,x,0,-w); 44 } 45 46 OwO spfa(QAQ s,QAQ t){ 47 F(i,s,t) dis[i]=oo,vis[i]=0; 48 dis[t]=0;vis[t]=1; 49 q.push(t); 50 while(!q.empty()){ 51 QAQ x=q.front();q.pop();vis[x]=0; 52 for(QAQ i=head[x];i;i=a[i].last) if(a[i^1].rem&&dis[a[i].to]>dis[x]-a[i].val){ 53 dis[a[i].to]=dis[x]-a[i].val; 54 if(!vis[a[i].to]) vis[a[i].to]=1,q.push(a[i].to); 55 } 56 } 57 return dis[s]<oo; 58 } 59 60 QAQ dfs(QAQ x,QAQ want){ 61 if(x==t||!want) { 62 // vis[x]=1; 63 return want; 64 } 65 QAQ f=0; 66 vis[x]=1; 67 for(QAQ i=head[x];i;i=a[i].last) if(!vis[a[i].to]&&a[i].rem&&dis[a[i].to]==dis[x]-a[i].val){ 68 QAQ d=dfs(a[i].to,min(want-f,a[i].rem)); 69 if(d){ 70 ans+=d*a[i].val; 71 a[i].rem-=d; 72 a[i^1].rem+=d; 73 f+=d; 74 } 75 if(f==want) break; 76 } 77 vis[x]=0; 78 return f; 79 } 80 81 void zkw(){ 82 // QAQ ans=0; 83 while(spfa(s,t)){ 84 vis[t]=1; 85 while(vis[t]){ 86 MES(vis,0); 87 dfs(s,oo); 88 } 89 } 90 // return ans; 91 } 92 93 94 QAQ main(){ 95 scanf("%d",&n); 96 s=0;t=n+1; 97 F(i,1,n){ 98 QAQ k; 99 scanf("%d",&k); 100 if(k) Insert(i,t,k,0); 101 if(i!=1) Insert(i,1,oo,0); 102 while(k--){ 103 QAQ v,w; 104 scanf("%d%d",&v,&w); 105 Insert(s,v,1,w); 106 Insert(i,v,oo,w); 107 } 108 } 109 zkw(); 110 printf("%d\n",ans); 111 return 0; 112 } View Code
转载于:https://www.cnblogs.com/heower/p/8491322.html
