首页 > 代码库 > 【最小路径覆盖】【二分图】【最大流】【Dinic】bzoj2150 部落战争
【最小路径覆盖】【二分图】【最大流】【Dinic】bzoj2150 部落战争
裸的最小路径覆盖。
把每个点拆点，变成二分图。
对于可以连边的点对(i,j):i->j‘(1);
对于任意一点i,若i点为‘.‘:S->i(1),i‘->T(1);
答案为所有‘.‘的数量-最大流(最大匹配数)。
引用证明：
路径覆盖中的每条简单路径除了最后一个顶点之外都有唯一的后继和它对应；因此匹配边数就是非路径结尾的结点数；因此，匹配边数达到最大时，非路径结尾的结点数大道最大，故路径结尾的节点数目最少。
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define INF 2147483647#define MAXN 5011#define MAXM 5000301int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM];int d[MAXN],cur[MAXN];queue<int>q;int n,m,S,T,N,M,R,C;void Init_Dinic(){memset(first,-1,sizeof(first)); en=0; n=N*M; S=0; T=N*M+1;}void AddEdge(const int &U,const int &V,const int &W){v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++;v[en]=U; next[en]=first[V]; first[V]=en++;}bool bfs(){ memset(d,-1,sizeof(d)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==-1 && cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1;}int dfs(int U,int a){ if(U==T || !a) return a; int Flow=0,f; for(int &i=cur[U];i!=-1;i=next[i]) if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow;}int max_flow(){ int Flow=0,tmp=0; while(bfs()) { memcpy(cur,first,((n<<1)+5)*sizeof(int)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow;}char map[52][52];int num[52][52],sumv;bool check(int x1,int y1,int x2,int y2){ if(x2<=N && x2>=1 && y2<=M && y2>=1 && map[x2][y2]==‘.‘) AddEdge(num[x1][y1],num[x2][y2]+n,1);}int main(){ scanf("%d%d%d%d",&N,&M,&R,&C); Init_Dinic(); for(int i=1;i<=N;++i) scanf("%s",map[i]+1); for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) num[i][j]=++en; Init_Dinic(); for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) if(map[i][j]==‘.‘) { ++sumv; AddEdge(S,num[i][j],1); AddEdge(num[i][j]+n,T,1); check(i,j,i+R,j+C); check(i,j,i+R,j-C); if(R!=C) { check(i,j,i+C,j+R); check(i,j,i+C,j-R); } } printf("%d\n",sumv-max_flow()); return 0;}
【最小路径覆盖】【二分图】【最大流】【Dinic】bzoj2150 部落战争
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。