[BZOJ1779][Usaco2010 Hol]Cowwar 奶牛战争（最大流）

题目描述

传送门

题解

一眼网络流啊。。。 对于所有的J，s->i,1 对于所有的T，i->t,1 将J和E再拆两个点xi,yi，连边xi->yi,1 对于每一个J能移动到的位置（J或E），连边i->xj,1 对于每一个位置（J或E）能攻击到的T，连边yi->j,1 跑最大流即可 即用流来模拟了攻击的过程

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; #define N 160000 #define inf 2100000000 int n,m,s,t,maxflow;bool e[1005][1005]; char str[N]; int tot,point[N],nxt[N],v[N],remain[N]; int deep[N],last[N],cur[N],num[N]; queue <int> q; void addedge(int x,int y,int cap) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; } void bfs(int t) { for (int i=1;i<=t;++i) deep[i]=t; deep[t]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; q.push(t); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&remain[i^1]) { deep[v[i]]=deep[now]+1; q.push(v[i]); } } } int addflow(int s,int t) { int now=t,ans=inf; while (now!=s) { ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans; } void isap(int s,int t) { bfs(t); for (int i=1;i<=t;++i) ++num[deep[i]]; int now=s; while (deep[s]<t) { if (now==t) { maxflow+=addflow(s,t); now=s; } bool has_find=0; for (int i=cur[now];i!=-1;i=nxt[i]) if (deep[v[i]]+1==deep[now]&&remain[i]) { has_find=1; cur[now]=i; last[v[i]]=i; now=v[i]; break; } if (!has_find) { int minn=t-1; for (int i=point[now];i!=-1;i=nxt[i]) if (remain[i]) minn=min(minn,deep[v[i]]); if (!(--num[deep[now]])) break; ++num[deep[now]=minn+1]; cur[now]=point[now]; if (now!=s) now=v[last[now]^1]; } } } int main() { scanf("%d%d",&n,&m); scanf("%s",str+1); for (int i=1;i<=m;++i) { int x,y;scanf("%d%d",&x,&y); e[x][y]=e[y][x]=1; } s=3*n+1,t=s+1; tot=-1;memset(point,-1,sizeof(point)); for (int i=1;i<=n;++i) { if (str[i]=='J') { addedge(s,i,1); addedge(i,n+i,1); addedge(n+i,n+n+i,1); for (int j=1;j<=n;++j) if (e[i][j]&&str[j]!='T') addedge(i,n+j,1); } if (str[i]=='T') { addedge(i,t,1); for (int j=1;j<=n;++j) if (e[i][j]&&str[j]!='T') addedge(n+n+j,i,1); } if (str[i]=='E') addedge(n+i,n+n+i,1); } isap(s,t); printf("%d\n",maxflow); }