思路：
1.按照题意求最小割 转换成最大流用Dinic解 2. 转换成对偶图 求最短路 Dinic：//By SiriusRen#include#include #include #include using namespace std;#define N 1100000int n,m,first[N],next[N*6],v[N*6],w[N*6],tot,jy,ans,vis[N],S,T,xx,pos[N];void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}void add(int x,int y,int z){Add(x,y,z),Add(y,x,z);}bool tell(){ memset(vis,-1,sizeof(vis)),vis[S]=0; queue q;q.push(S); while(!q.empty()){ int t=q.front();q.pop(); for(int i=first[t];~i;i=next[i]) if(w[i]&&vis[v[i]]==-1) vis[v[i]]=vis[t]+1,q.push(v[i]); }return vis[T]!=-1;}int zeng(int x,int y){ if(x==T)return y; int r=0; for(int i=first[x];~i&&y>r;i=next[i]) if(w[i]&&vis[v[i]]==vis[x]+1){ int t=zeng(v[i],min(y-r,w[i])); w[i]-=t,w[i^1]+=t,r+=t; } if(!r)vis[x]=-1; return r;}int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&n,&m); S=m+1,T=n*m+m; for(int i=1;i<=n;i++)for(int j=1;j
Dijkstra：
这么转成对偶图 在原平面图中添加一条从起点S到终点T的边，会增加一个区域S’。 无限大的区域设为T’。 把加边后的平面图按照上面的方法转化为对偶图。 删去边S’-T’。 此时S-T的最小割大小等于S’到T’的最短路长度。 Ps：需要特判n=1|m=1的情况
//By SiriusRen#include#include #include using namespace std;#define M 1111*1111*6int n,m,a[1005][1005],b[1005][1005],c[1005][1005],T=2000*1005;int first[M/3],next[M],v[M],w[M],tot,vis[M/3],d[M/3];void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}struct Node{ int now,weight;}jy;bool operator < (Node a,Node b){ return a.weight>b.weight;}void Dijkstra(){ priority_queue pq;pq.push(jy); while(!pq.empty()){ Node t=pq.top();pq.pop(); if(vis[t.now])continue; for(int i=first[t.now];~i;i=next[i])if(d[v[i]]>d[t.now]+w[i]) d[v[i]]=d[t.now]+w[i],jy.now=v[i],jy.weight=d[v[i]],pq.push(jy); }printf("%d\n",d[T]=0x3f3f3f3f?d[T]:0);}void add(int x,int y,int z){Add(x,y,z),Add(y,x,z);}int main(){ memset(first,-1,sizeof(first)),memset(d,0x3f,sizeof(d)),d[0]=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)for(int j=1;j
