【HDU3870 Catch the Theves】最小割与最短路模型进行转换

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3870

题目大意：O(-1).

解题思路：开始直接构图，套Dinic（）模板，悲剧的TLE。再认真看看题，n为400，也就是有400*400个点，边大概是节点的4倍大小,明显最大流会TLE，对偶图构图很蛋疼。

对于点数边数很大的求最小割来说，可以构造它的对偶图，构造对偶图要求原图中s和d必须在图的外侧，对偶图G*中的每个点对应G中一个面，每一条从st到sd的最短路径都对应原图s到d的一个最小割。

构造对偶图条件：

1、原图是一个平面图

2、图中的一个点为源点s，另外一个点为汇点t，且s和t都在图中的无界面的边界上

G*中的每个点对应G中一个面

参考文献：周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》.

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int mn=422222;
 8 const int mm=2111111;
 9 const int oo=0x3fffffff;
10 int que[mn], inque[mn], dis[mn];
11 int head[mn], reach[mm], flow[mm], next[mm];
12 int st, sd, edge;
13 int val[444][444];
14 
15 void addedge(int u, int v, int c1, int c2)
16 {
17     reach[edge]=v, flow[edge]=c1, next[edge]=head[u], head[u]=edge++;
18     reach[edge]=u, flow[edge]=c2, next[edge]=head[v], head[v]=edge++;
19 }
20 
21 void spfa()
22 {
23     for(int i=1; i<=sd+5; i++) inque[i]=0, dis[i]=oo;
24     int h=0, t=0;
25     dis[st]=0;
26     que[t++]=st;
27     inque[st]=1;
28     while(h!=t)
29     {
30         int u=que[h++];
31         if(h==mn) h=0;  ///！循环队列
32         inque[u]=0;
33         for(int i=head[u]; i>=0; i=next[i])
34         {
35             int v=reach[i], val=flow[i];
36             if(dis[v]>dis[u]+val)  ///当满足这个条件时才进行下面的操作
37             {
38                 dis[v]=dis[u]+val; ///松弛操作
39                 if(!inque[v])
40                 {
41                     inque[v]=1;
42                     que[t++]=v;
43                     if(t==mn) t=0; ///循环队列
44                 }
45             }
46         }
47     }
48 }
49 
50 int main()
51 {
52     int n, m, T;
53     cin >> T;
54     while(T--)
55     {
56         scanf("%d",&n);
57         st=0, sd=n*n+1;
58         memset(head,-1,sizeof(head));
59         for(int i=1; i<=n; i++)
60             for(int j=1; j<=n; j++) scanf("%d",&val[i][j]);
61         for(int i=1; i<n; i++)
62         {
63             addedge(st,i,val[1][i],val[1][i]);
64             addedge(st,(i-1)*(n-1)+(n-1),val[i][n],val[i][n]);
65             addedge((i-1)*(n-1)+1,sd,val[i][1],val[i][1]);
66             addedge((n-2)*(n-1)+i,sd,val[n][i],val[n][i]);
67         }
68         for(int i=1; i<=n-1; i++)
69             for(int j=1; j<=n-1; j++)
70             {
71                 if(j+1<=n-1)addedge((i-1)*(n-1)+j,(i-1)*(n-1)+j+1,val[i][j+1],val[i][j+1]);
72                 if(i+1<=n-1)addedge((i-1)*(n-1)+j,i*(n-1)+j,val[i+1][j],val[i+1][j]);
73             }
74         spfa();
75         printf("%d\n",dis[sd]);
76     }
77     return 0;
78 }

【HDU3870 Catch the Theves】 最小割与最短路模型进行转换

【HDU3870 Catch the Theves】最小割与最短路模型进行转换