遇到这种整列整行的题可以考虑用一个节点表示整一列或者建一个虚拟节点向这一列的每个点连边。
然后最小割的定义:把所有节点分到分别包含 \(S\) 和 \(T\) 的两个集合内,求 \(S\) 所在集合指向 \(T\) 所在集合的所有边的边权和的最小值。
也就是割成两半的最小代价,这个可以联想到:
-
图论,把图分成两半的最小代价。
-
很多人做选择,做完选择的最小代价。
这道题就是联想到了第 \(1\) 点。
代码如下:
#include<bits/stdc++.h>
#define N 110
#define INF 0x7fffffff
#define get(x,y) ((x-1)*m+y)
using namespace std;
int n,m,s,t,stx,sty,edx,edy;
int cnt=1,head[N<<1],cur[N<<1],to[N*N*4],nxt[N*N*4],c[N*N*4];
int num[N<<1];
char ch[N][N];
queue<int>q;
void adde(int u,int v,int ci)
{
to[++cnt]=v;
c[cnt]=ci;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
c[cnt]=0;
nxt[cnt]=head[v];
head[v]=cnt;
}
bool bfs()
{
memset(num,-1,sizeof(num));
memcpy(cur,head,sizeof(cur));
q.push(s);
num[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]&&num[v]==-1)
{
num[v]=num[u]+1;
q.push(v);
}
}
}
return num[t]!=-1;
}
int dfs(int u,int minflow)
{
if(!minflow||u==t) return minflow;
int preflow=0,nowflow;
for(int i=cur[u];i;i=nxt[i])
{
cur[u]=i;
int v=to[i];
if(num[v]==num[u]+1&&(nowflow=dfs(v,min(minflow-preflow,c[i]))))
{
preflow+=nowflow;
c[i]-=nowflow;
c[i^1]+=nowflow;
if(!(minflow-preflow)) break;
}
}
return preflow;
}
int dinic()
{
int maxflow=0;
while(bfs())
maxflow+=dfs(s,INF);
return maxflow;
}
int main()
{
scanf("%d%d",&n,&m);
s=1,t=1+n+m+1;
for(int i=1;i<=n;i++)
{
scanf("%s",ch[i]+1);
for(int j=1;j<=m;j++)
{
if(ch[i][j]=='o')
{
adde(1+i,1+n+j,1);
adde(1+n+j,1+i,1);
}
if(ch[i][j]=='S')
{
stx=i,sty=j;
adde(s,1+i,INF);
adde(s,1+n+j,INF);
}
if(ch[i][j]=='T')
{
edx=i,edy=j;
adde(1+i,t,INF);
adde(1+n+j,t,INF);
}
}
}
if(stx==edx||sty==edy)
{
puts("-1");
return 0;
}
printf("%d\n",dinic());
return 0;
}
原文地址:http://www.cnblogs.com/ez-lcw/p/16837093.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性