【题目链接】
http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1779
【题目大意】
有n个点，m条边的无向图。
上面的点一开始要么是J牛，要么是T牛，要么是E，表示没有牛。
然后J牛有两种选择：
1、直接攻击自己附近的一只T牛，然后停住永远不动。
2、向邻近的点走一步，然后攻击or不攻击附近的一只T牛，然后停住永远不动。
特别得，
J牛不能跑进任何一只本身有牛的点。
T牛不会动。并且只能被打死一次。然后就算他死了，J牛也不能进入他的领土（他的灵魂开无敌了）!!!
然后他们动都有先后顺序，然后问最多能打死多少只T牛。
【算法分析】
建立一个4层的图。
第一层，给每只J牛赋予1的流量。
第二层，每只J牛要么停在原来这个点，要么走一步，到达另外一个点。
流量可以跟随这只牛的脚步走过去。
当然，到达的点不能是T牛占得点。
第三层，从第二层的对应点中引一条容量为1的边到第三层的对应点，那么就对应于：每个点只能有一只牛。
第四层，那些牛们“站位”已经到了最好状态，开始攻击T牛，即每个“非T牛”的点像每只T牛点连一个容量为1的边，然后T牛们就可以向汇点连容量为1的边。
这样，就完成了最终的匹配。
这个用最大流实现即可。输出方案利用残余图不难得出。当然，我写得是无方案版。
【CODE】
/*
ID:jie22221
TASK:cowwar
LANG:C++
*/
#include
#define clr(a) memset(a,0,sizeof(a))
const int N=30000;
const int INF=1000000000;
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
edge *ls[N],*cur[N];
int vs,vt,d[N],Flow,Q[N];
void addedge(int x,int y,int c){
edge *p=(edge*)malloc(sizeof(edge));
edge *q=(edge*)malloc(sizeof(edge));
p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
}
int dfs(int p,int nf){
if (p==vt) return nf;
int tmp,FF=0;
for (edge *&t=cur[p];t;t=t->next)
if (t->c && d[t->x]+1==d[t->y] && (tmp=dfs(t->y,min(nf,t->c)))){
FF+=tmp;
t->c-=tmp; t->op->c+=tmp;
if (!(nf-=tmp)) break;
}
if (!cur[p]) d[p]=INF;
return FF;
}
bool bfs(){
for (int i=0;i<=vt;i++){
d[i]=INF;
cur[i]=ls[i];
}
d[vs]=1; Q[1]=vs;
for (int st=1,ed=1;d[Q[st]]
if (t->c && d[t->y]==INF) d[ Q[++ed]=t->y ]=d[t->x]+1;
if (d[vt]==INF) return false;
return true;
}
void dinic(){
Flow=0;
int tmp;
while (bfs())
while (tmp=dfs(vs,INF)) Flow+=tmp;
}
}Network;
struct Node{int y;Node *next;};
struct Link_t{
Node *ls[N];
void addedge(int x,int y){
Node *p=(Node*)malloc(sizeof(Node));
p->y=y; p->next=ls[x]; ls[x]=p;
}
}Link;
int n,m;
char str[N];
void init(){
clr(Link.ls);
clr(Network.ls);
scanf("%d%d%s",&n,&m,str+1);
for (int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
Link.addedge(x,y);
Link.addedge(y,x);
}
}
void build(){
Network.vs=0; Network.vt=n*4+1;
for (int i=1;i<=n;i++){
if (str[i]==’J’){
Network.addedge(Network.vs,i,1);
Network.addedge(i,n+i,1);
for (Node *t=Link.ls[i];t;t=t->next)
if (str[t->y]!=’T’)
Network.addedge(i,n+t->y,1);
}
if (str[i]==’T’)
Network.addedge(3*n+i,Network.vt,1);
else{
for (Node *t=Link.ls[i];t;t=t->next)
if (str[t->y]==’T’)
Network.addedge(2*n+i,3*n+t->y,1);
Network.addedge(n+i,2*n+i,1);
}
}
}
int main(){
freopen("cowwar.in","r",stdin);
freopen("cowwar.out","w",stdout);
init();
build();
Network.dinic();
printf("%dn",Network.Flow);
}