[USACO2010 Hol 【cowwar】]最大的三重匹配,最大流

【题目链接】

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 #include #include #define min(x,y) ((x)<(y)?(x):(y))
#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]]              for (edge *t=ls[Q[st]];t;t=t->next)
                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);
}

留下评论

您的电子邮箱地址不会被公开。