http://www.lydsy.com/JudgeOnline/problem.php?id=1779

题意

太复杂了。。所以

http://www.nocow.cn/index.php/USACO/cowwar

题解

这题感觉就是利用网络流，瞪眼建模，通过流量来满足条件。

http://www.dxmtb.com/blog/usaco2010-hol-cowwar/

1.一个E点拆成两个点。把一个J点拆成三个点。T点不变。

2.从原点向每个J的第一个点连一条边容量为1，表示只有一只牛。

3.从J的第一个点连边到能到的点。能到的J点连第二个点，能到的E点连第一个点，容量都为1。注意，J也能到他自己。

4.对于每个能攻击的J点，把第三个J点连一条容量为1的边到能攻击的T。对于每个能攻击的E点，把第二个E点连到能攻击的T点，容量还是1。

5.把E的第一个点连一条容量为1的边到第二个点，表示只能从这个点攻击一次。J的第二个点连一条容量为1的边到第三个点，也表示只能从这个点攻击一次。

6.每个T点连一条边到汇点，容量为1。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=3005,M=100000;
int u[M],v[M],w[M],next[M],head[N],k=1;
int low[N],pre[N],d[N],vd[N],cur[N];
int n,m;
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
int solve(int s,int t)
{
    int now=s,i,ans=0;
    low[s]=INT_MAX;vd[0]=t;
    while(d[s]<t)
    {
        for(i=cur[now];i;i=next[i])
            if(w[i]>0 && d[now]==d[v[i]]+1)
                break;
        cur[now]=i;
        if(i)
        {
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i];
            if(now==t)
            {
                for(;now!=s;now=u[pre[now]])
                {
                    w[pre[now]]-=low[t];w[pre[now]^1]+=low[t];
                }
                low[s]=INT_MAX;ans+=low[t];
            }
        }
        else
        {
            if(!--vd[d[now]])   break;
            d[now]=t;
            for(i=head[now];i;i=next[i])
                if(w[i]>0 && d[now]>d[v[i]]+1)
                {
                    d[now]=d[v[i]]+1;
                    cur[now]=i;
                }
            vd[d[now]]++;
            if(now!=s)  now=u[pre[now]];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    char c[N];scanf("%s",c+1);
    int S=0,T=n*3+1;
    for(int i=1;i<=n;i++)
    {
        if(c[i]=='J')
        {
            add(S,i,1);
            add(i,i+n,1);
            add(i+n,i+n+n,1);
        }
        if(c[i]=='T')   add(i,T,1);
        if(c[i]=='E')   add(i,i+n,1);
    }
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        if(c[y]=='J')   swap(x,y);
        if(c[x]=='J')
        {
            if(c[y]=='T')   add(x+n+n,y,1);
            if(c[y]=='J')   add(x,y+n,1),add(y,x+n,1);
            if(c[y]=='E')   add(x,y,1);
        }
        if(c[x]=='T')
            if(c[y]=='E')
                add(y+n,x,1);
        if(c[x]=='E')
            if(c[y]=='T')
                add(x+n,y,1);
    }
    printf("%d\n",solve(S,T));
}