最小割= =这道题都是做最小割例题来讲的，终于真正写了一次. 先黑白染色 源点向黑点连容量为num的边 黑点向白点连容量为inf的边 白点向汇点连容量为nun的边 跑最小割，也就是最大流 建图很简单但是很难理解，我的理解就是为了把他们分开选取了最小的割，剩下的图中的点就是不连通的了，感觉比赛的时候出一道最小割绝对做不出来啊QAQ，感觉最小割的建图太难yy了.
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<queue>using namespace std;const int N=2000,inf=0x3f3f3f3f;int pic[50][50],num[N],cur[N],p[N],d[N],head[N];int n,m,t,s,te,sz,tot;struct edge{ int u,v,cap,flow,next;}e[20010];queue<int>q;void add(int u,int v,int cap){ e[++te].u=u; e[te].v=v; e[te].flow=0; e[te].cap=cap; e[te].next=head[u]; head[u]=te;}void insert(int u,int v,int cap){add(u,v,cap),add(v,u,0);}void bfs(){ memset(d,0,sizeof(d)); while(!q.empty())q.pop(); q.push(t); while(!q.empty()) { int v=q.front(); for (int i=head[v];i;i=e[i].next) { int u=e[i].v; if (e[i].cap==0&&!d[u]) { d[u]=d[v]+1; q.push(u); } } q.pop(); }}int augment(){ int a=inf,x=t; while(x!=s) { a=min(e[p[x]].cap-e[p[x]].flow,a); x=e[p[x]].u; } x=t; while(x!=s) { e[p[x]].flow+=a; e[p[x]^1].flow-=a; x=e[p[x]].u; } return a;}int isap(){ int flow=0,x=s; copy(head,head+n+1,cur); memset(num,0,sizeof(num)); bfs(); for (int i=1;i<=n;i++) num[d[i]]++; while(d[s]<n) { if (x==t) { flow+=augment(); x=s; } int ok=0; for (int i=cur[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow&&d[v]+1==d[x]) { p[v]=i; ok=1; cur[x]=i; x=v; break; } } if (!ok) { if (--num[d[x]]==0)break; int mx=n-1; for (int i=head[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow)mx=min(mx,d[v]); } ++num[d[x]=mx+1]; cur[x]=head[x]; if (x!=s)x=e[p[x]].u; } } return flow;}int main(){ cin>>n>>m; te=1,sz=n*m,s=sz+1,t=sz+2,tot=0; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { scanf("%d",&pic[i][j]); tot+=pic[i][j]; if ((i+j)&1) { insert(s,(i-1)*m+j,pic[i][j]); if (i>1)insert((i-1)*m+j,(i-2)*m+j,inf); if (i<n)insert((i-1)*m+j,i*m+j,inf); if (j>1)insert((i-1)*m+j,(i-1)*m+j-1,inf); if (j<m)insert((i-1)*m+j,(i-1)*m+j+1,inf); } else insert((i-1)*m+j,t,pic[i][j]); } } n=t;// for (int i=2;i<=te;i+=2)// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].cap<<endl; cout<<tot-isap(); }新闻热点
疑难解答
