首页 > 代码库 > HDU 1565 （最大流+黑白染色化二分图求最小割）
HDU 1565 （最大流+黑白染色化二分图求最小割）
http://acm.hdu.edu.cn/showproblem.php?pid=1565
思路：将横纵坐标和为偶尔染白色，其他染黑色，黑点连接源点，流量为该点的值，白点连接汇点，流量为该点的值，黑白点有相邻的就连边，值为无穷大。最后求最大流，即该图的最小割。
PS：刚开始不明白为为什么最大流会等于最小割，为什么所有的点之和减去最小割就会等于答案。
我的理解是：整张图其实就跟连接管道一样，连接了黑点表示取了黑点那个值的流量，白点也是，而连接了相邻的黑白点求出的最大流就会是流量较小的那个的值。好比三根管道连接，流量分别是white，black，inf_max，这样求出来的肯定是min（white，black，inf_max），所以只要去掉这些割边所对应的值的和，剩下的就是答案的最大值了。
1 /*Dinic算法求最大流*/ 2 #include<stdio.h> 3 #include<string.h> 4 #include<iostream> 5 #define point_MAX 10000 6 #define edge_MAX 100000 7 #define INF_MAX 999999999 8 using namespace std; 9 struct EDGE 10 { 11 int to;/*指向的点*/ 12 int next;/*指向的下一条邻边*/ 13 int w;/*权值*/ 14 }edge[edge_MAX]; 15 int len;/*边的数量*/ 16 int point[point_MAX]; 17 int Vertex,Edge; 18 int d[point_MAX]; 19 void init()/*初始化*/ 20 { 21 len=0; 22 memset(point,0,sizeof(point)); 23 } 24 int add_edge(int a,int b,int w)/*添加由a指向b的权值为w的边*/ 25 { 26 len++; 27 edge[len].w=w; 28 edge[len].to=b; 29 edge[len].next=point[a]; 30 point[a]=len; 31 return 0;/*无重边，插入*/ 32 } 33 int bfs(int s) 34 { 35 int q[point_MAX],front=0,rear=1,j,t,i; 36 q[0]=s; 37 memset(d,-1,sizeof(d));/**/ 38 d[s]=0; 39 while(front<rear) 40 { 41 t=q[front++]; 42 for(j=point[t];j;j=edge[j].next) 43 { 44 if(d[edge[j].to]==-1&&edge[j].w>0) 45 { 46 d[edge[j].to]=d[t]+1; 47 q[rear++]=edge[j].to;/*逐层增加*/ 48 } 49 } 50 } 51 if(d[Vertex]>=0) 52 return 1; 53 return 0; 54 } 55 long long min(long long a,long long b) 56 { 57 return a<b?a:b; 58 } 59 long long dinic(int t,long long sum)/*寻找增广路*/ 60 { 61 int i,os,j; 62 long long a; 63 if(t==Vertex)/*如果已经找到汇点，返回sum*/ 64 return sum; 65 os=sum; 66 for(i=point[t];i&∑i=edge[i].next) 67 { 68 if(d[edge[i].to]==d[t]+1&&edge[i].w>0)/*可行流，即增广路*/ 69 { 70 a=dinic(edge[i].to,min(sum,edge[i].w)); 71 edge[i].w-=a; 72 for(j=point[edge[i].to];edge[j].to!=t;j=edge[j].next); 73 edge[j].w+=a;/*处理反向边*/ 74 sum-=a; 75 } 76 } 77 return os-sum; 78 } 79 long long DINIC(int s)/*DINIC算法*/ 80 { 81 long long ans=0; 82 while(bfs(s))/*遍历整个图，判断是否已经完成最大流*/ 83 ans+=dinic(s,INF_MAX);/*添加所能增加的流量*/ 84 return ans; 85 } 86 int abs(int a) 87 { 88 return a>0?a:(-a); 89 } 90 int main() 91 { 92 int i,j,x,y,w,S,D; 93 int cost[25][25],num[25][25],col[25][25]; 94 while(scanf("%d",&Vertex)!=EOF) 95 { 96 init(); 97 int NUM=1; 98 long long sum=0; 99 for(i=1;i<=Vertex;i++)100 for(j=1;j<=Vertex;j++)101 {102 scanf("%d",&cost[i][j]);103 sum+=cost[i][j];104 num[i][j]=NUM++;105 if((i+j)&1)col[i][j]=1;//黑白染色，即化为二分图106 else col[i][j]=0;107 }108 for(i=1;i<=Vertex;i++)109 {110 for(j=1;j<=Vertex;j++)111 {112 int s=num[i][j];113 if(col[i][j]&1)//奇数点/黑点连在源点上114 {115 add_edge(0,s,cost[i][j]);116 add_edge(s,0,0);//反向边117 for(int k=1;k<=Vertex;k++)118 for(int l=1;l<=Vertex;l++)119 {120 if(abs(i-k)+abs(j-l)==1&&!(col[k][l]&1))121 {122 //printf("%d->%d\n",s,num[k][l]);123 add_edge(s,num[k][l],INF_MAX);124 add_edge(num[k][l],s,0);125 }126 }127 }128 else129 {130 add_edge(s,NUM,cost[i][j]);131 add_edge(NUM,s,0);//反向边132 /*for(int k=1;k<=Vertex;k++)133 for(int l=1;l<=Vertex;l++)134 {135 if(abs(i-k)+abs(j-l)==1&&(num[k][l]&1))136 {137 //printf("%d->%d\n",s,num[k][l]);138 add_edge(num[k][l],s,INF_MAX);139 add_edge(s,num[k][l],0);140 }141 }*/142 }143 }144 }145 Vertex=NUM;146 //cout<<"=="<<endl;147 cout<<sum-DINIC(0)<<endl;/*以S为源点，Vertex为汇点*/148 }149 return 0;150 }151 /*152 3153 75 15 21154 75 15 28155 34 70 5156 3157 906 864 217158 502 517 839159 996 39 29160 161 */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。