題目大意: 現在有一項工程,有n(n<=5000,編號1~n)個站點可以建立,建立i站點需要花費pi. 而假設a站點和b站點均建立了,那麼可以獲利C<a,b>,這樣的關系有m個(m<=50000). 問建立那些站點可獲得最大純利潤. 題目思路: 裸的最大權閉合圖. 這種題型的建圖有兩種方法. 一:(建完後的圖的原圖完全不同) (1)將所有邊看成點(成為利潤點),並各向構成這條邊的兩個點建立一條容量為正無窮大的邊. (3)用源點(建立一個超級源點)向所有利潤點建立一條容量為其獲利的邊. (2)將原來所有點(成為花費點),向匯點(建立一個超級匯點)建立一條容量為其花費的邊. 這樣之後就是要求出該圖的最小割,而且最小割必然是割在和源點或者匯點相連的邊上,因為其余的邊容量均為無窮大. www.2cto.com 通俗的說最小割的割集就是我們不需要的建立的站點的花費和無法獲利的邊. 這種方法的正確性,其實可以這樣考慮,從源點到匯點必然是這樣的路徑: 源點--->利潤邊--->花費邊--->匯點, 而最小割肯定是割在這三條邊上容量最小的一條. 將問題轉為最小割之後,由於最小割容量等於最大流,所以用所有利潤邊的獲利和減去求得最大流即可. 二:(只需要在原圖的基礎上改進) 對於第一種我們可以分析, 點數=n+m+2,n最大是5000,m最大是50000,所以構造出來的圖會有55002個點. 邊數=n+m+m,大概11萬條邊. 顯然這是一個 很龐大的圖,效率並不好. 所以我們需要一個更好的建模方式. (1)同樣需要一個超級源點S,一個超級匯點T. (2)源點連向所有點,容量為U (U為所有獲利的和),稱為零邊. (3)所有點連向匯點,容量為U+2*pi-di (di為所有所有和i相關聯的邊的權值和),稱為差邊. ps:U的作用是為了使差邊的容量非負. 這樣我們可以看一下從源點到匯點的路徑是什麼樣的. 假設原圖中存在一條利潤邊a-->b 那麼必然存在這樣幾條路徑使得S和T連通. S ---> a ---> T S ---> b ---> T S ---> a ---> b ---> T S ---> b ---> a ---> T 為了使得S和T不連通,那麼最小割可能為以下兩種. S ---> a 和 S ---> b ,即都割零邊,割的容量為2U a ---> T 和 b ---> T ,即都割差邊,割的容量為2U+2*(pa+pb)-(va+vb) S ---> a 和 b ---> a 和 b ---> T , 即割零邊和差邊,割的容量為2U+2*pb-vb+weight(a,b). S ---> b 和 a ---> b 和 a ---> T , 即割零邊和差邊,割的容量為2U+2*pa-va+weight(a,b). 如果割零邊,表示a站點和b站點都不建立,顯然利潤為0. 反之,a和b 都建立,利潤應該是 weigt(a,b)-(pa+pb). 如果與a,與b關聯的邊均只有一條,即(a,b),那麼va = vb = weigt(a,b). 那麼割差邊時,割的容量2U+2*(pa+pb)-(va+vb) =2U+2*(pa+pb)-2*weigt(a,b). 假設還有一割點c與a關聯,且除a沒有其他點和c關聯. 1).假設c站點建立,那麼多了一個割為c ---> T. 那麼割的容量為 3U+2*(pa+pb+pc)-(va+vb+vc) = 3U+2*(pa+pb+pc)-2*(weigt(a,b)+weight(a,c)). 2).假設c站點不建立,那麼多兩個割為S ---> c 和 a ---> c 那麼割的容量為 3U+2*(pa+pb) - (va+vb) + weight(a,c) = 3U+2*(pa+pb)-2*weigt(a,b)-weight(a,c)+weight(a,c) = 3U+2*(pa+pb)-2*weigt(a,b) 同理可證當c或b還有其他關聯邊時也滿足該式子. 又所以利潤 = (nU-割[S,T])/2. 代碼(一): [cpp] #include <stdlib.h> #include <string.h> #include <stdio.h> #include <ctype.h> #include <math.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <string> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ls rt<<1 #define rs ls|1 #define lson l,mid,ls #define rson mid+1,r,rs #define middle (l+r)>>1 #define eps (1e-8) #define clr_all(x,c) memset(x,c,sizeof(x)) #define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1)) #define MOD 1000000009 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define _max(x,y) (((x)>(y))? (x):(y)) #define _min(x,y) (((x)<(y))? (x):(y)) #define _abs(x) ((x)<0? (-(x)):(x)) #define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x)) #define getmax(x,y) (x= ((y)>(x))? (y):(x)) template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;} int TS,cas=1; const int M=60000+5; int n,m; struct sap{ typedef int type; struct edge{ int to,next; type flow; }edg[999999]; int n,m; int g[M],cur[M],pre[M]; int dis[M],gap[M]; int q[M],head,tail; void init(int _n){n=_n,m=0,clr_all(g,-1);} void insert(int u,int v,type f,type c=0){ edg[m].to=v,edg[m].flow=f,edg[m].next=g[u],g[u]=m++; edg[m].to=u,edg[m].flow=0,edg[m].next=g[v],g[v]=m++; } bool bfs(int s,int t){ clr(gap,0,n),clr(dis,-1,n); gap[dis[t]=0]++,dis[s]=-1; for(q[head=tail=0]=t;head<=tail;){ int u=q[head++]; for(int i=g[u];i!=-1;i=edg[i].next){ edge& e=edg[i],ee=edg[i^1]; if(dis[e.to]==-1 && ee.flow>0){ gap[dis[e.to]=dis[u]+1]++; q[++tail]=e.to; } } } return dis[s]!=-1; } type maxFlow(int s,int t){ if(!bfs(s,t)) return 0; type res=0,a; int i; for(i=0;i<n;i++) cur[i]=g[i]; pre[s]=s,cur[s]=g[s],cur[t]=g[t]; for(int u=s;dis[s]<n;){ if(u==t){ for(a=-1;u!=s;u=pre[u]) getmin(a,edg[cur[pre[u]]].flow); for(u=t;u!=s;u=pre[u]){ edg[cur[pre[u]]].flow-=a; edg[cur[pre[u]]^1].flow+=a; } res+=a; } bool ok=0; for(i=cur[u];i!=-1;i=edg[i].next){ edge& e=edg[i]; if(dis[u]==dis[e.to]+1 && e.flow>0){ cur[u]=i,pre[e.to]=u,u=e.to; ok=1;break; } } if(ok) continue; int mindis=n-1; for(i=g[u];i!=-1;i=edg[i].next){ edge& e=edg[i]; if(mindis>dis[e.to] && e.flow>0) mindis=dis[e.to],cur[u]=i; } if(--gap[dis[u]]==0) break; gap[dis[u]=mindis+1]++,u=pre[u]; } return res; } }p; void run(){ int i,j; p.init(n+m+2); int tot=0; for(i=1;i<=n;i++){ scanf("%d",&j); p.insert(i,n+m+1,j); } for(i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); p.insert(0,n+i,c); p.insert(n+i,a,INF); p.insert(n+i,b,INF); tot+=c; } printf("%d\n",tot-p.maxFlow(0,n+m+1)); } void preSof(){ } int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); preSof(); //run(); while(~scanf("%d%d",&n,&m)) run(); //for(scanf("%d",&TS);cas<=TS;cas++) run(); return 0; } 代碼(二): [cpp] #include <stdlib.h> #include <string.h> #include <stdio.h> #include <ctype.h> #include <math.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <string> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ls rt<<1 #define rs ls|1 #define lson l,mid,ls #define rson mid+1,r,rs #define middle (l+r)>>1 #define eps (1e-8) #define clr_all(x,c) memset(x,c,sizeof(x)) #define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1)) #define MOD 1000000009 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define _max(x,y) (((x)>(y))? (x):(y)) #define _min(x,y) (((x)<(y))? (x):(y)) #define _abs(x) ((x)<0? (-(x)):(x)) #define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x)) #define getmax(x,y) (x= ((y)>(x))? (y):(x)) template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;} int TS,cas=1; const int M=5000+5; int n,m,U; int pr[M],d[M]; int a[M*10],b[M*10],c[M*10]; struct sap{ typedef int type; struct edge{ int to,next; type flow; }edg[999999]; int n,m; int g[M],cur[M],pre[M]; int dis[M],gap[M]; int q[M],head,tail; void init(int _n){n=_n,m=0,clr_all(g,-1);} void insert(int u,int v,type uf,type vf=0){ edg[m].to=v,edg[m].flow=uf,edg[m].next=g[u],g[u]=m++; edg[m].to=u,edg[m].flow=vf,edg[m].next=g[v],g[v]=m++; } bool bfs(int s,int t){ clr(gap,0,n),clr(dis,-1,n); gap[dis[t]=0]++,dis[s]=-1; for(q[head=tail=0]=t;head<=tail;){ int u=q[head++]; for(int i=g[u];i!=-1;i=edg[i].next){ edge& e=edg[i],ee=edg[i^1]; if(dis[e.to]==-1 && ee.flow>0){ gap[dis[e.to]=dis[u]+1]++; q[++tail]=e.to; } } } return dis[s]!=-1; } type maxFlow(int s,int t){ if(!bfs(s,t)) return 0; type res=0,a; int i; for(i=0;i<n;i++) cur[i]=g[i]; pre[s]=s,cur[s]=g[s],cur[t]=g[t]; for(int u=s;dis[s]<n;){ if(u==t){ for(a=-1;u!=s;u=pre[u]) getmin(a,edg[cur[pre[u]]].flow); for(u=t;u!=s;u=pre[u]){ edg[cur[pre[u]]].flow-=a; edg[cur[pre[u]]^1].flow+=a; } res+=a; } bool ok=0; for(i=cur[u];i!=-1;i=edg[i].next){ edge& e=edg[i]; if(dis[u]==dis[e.to]+1 && e.flow>0){ cur[u]=i,pre[e.to]=u,u=e.to; ok=1;break; } } if(ok) continue; int mindis=n-1; for(i=g[u];i!=-1;i=edg[i].next){ edge& e=edg[i]; if(mindis>dis[e.to] && e.flow>0) mindis=dis[e.to],cur[u]=i; } if(--gap[dis[u]]==0) break; gap[dis[u]=mindis+1]++,u=pre[u]; } return res; } }p; void run(){ int i,j; p.init(n+1); int tot=0; for(i=1;i<=n;i++) scanf("%d",&pr[i]); clr(d,0,n); for(U=0,i=1;i<=m;i++){ scanf("%d%d%d",&a[i],&b[i],&c[i]); U+=c[i],d[a[i]]+=c[i],d[b[i]]+=c[i]; p.insert(a[i],b[i],c[i],c[i]); } for(i=1;i<=n;i++){ p.insert(0,i,U); p.insert(i,n+1,U+2*pr[i]-d[i]); } www.2cto.com printf("%d\n",(U*n-p.maxFlow(0,n+1))/2); } void preSof(){ } int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); preSof(); //run(); while(~scanf("%d%d",&n,&m)) run(); //for(scanf("%d",&TS);cas<=TS;cas++) run(); return 0; }
