HDU 3551 Hard Problem

http://acm.hdu.edu.cn/showproblem.php?pid=3551

题意:给出一个图，还有一个子图的度数，求有没有办法通过删边使得原图的度数变成那个子图的度数？

思路:我们考虑把每个点拆成du[i]-d[i]个点，代表要删去的度数，然后对于每条边，我们建立两个点eu,ev，eu与ev连边，如果这条边连接了i,j两个点，那么所有的i的点向eu连边，所有的j向ev连边，如果有完美匹配(就是所有点都有匹配)那么有解。

至于为什么:如果eu和ev是匹配边，代表这条边不删，因为这条边的两侧，也就是连接的两个点都有其他的匹配了，那么这条边就不用删。

如果这条边不是匹配边，那么说明i和eu匹配了，j和ev匹配了，这条边代表删掉了，而i和j的度数也-1了

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

struct edge{

    int u,v;

}e[];

int n,m,p[],q[];

int match[],newbase;

int inqueue[],inpath[],G[][],inblossom[],father[];

int du[],d[],c[],base[],start,finish,head,tail;

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

int lca(int u,int v){

    memset(inpath,,sizeof inpath);

    while (){

        u=base[u];

        inpath[u]=;

        if (!match[u]) break;

        u=father[match[u]];

    }

    while (){

        v=base[v];

        if (inpath[v]) break;

        v=father[match[v]];

    }

    return v;

}

void reset(int u){

    while (u!=newbase){

        int v=match[u];

        inblossom[base[v]]=inblossom[base[u]]=;

        u=father[v];

        if (base[u]!=newbase) father[u]=v;

    }

}

void blossomcontract(int u,int v){

    newbase=lca(u,v);

    memset(inblossom,,sizeof inblossom);

    reset(u);

    reset(v);

    if (base[u]!=newbase) father[u]=v;

    if (base[v]!=newbase) father[v]=u;

    for (int i=;i<=n;i++)

     if (inblossom[base[i]]){

            base[i]=newbase;

            if (!inqueue[i]) c[++tail]=i,inqueue[i]=;

     }

}

void findaugmentingpath(){

    memset(inqueue,,sizeof inqueue);

    memset(father,,sizeof father);

    for (int i=;i<=n;i++) base[i]=i;

    head=;tail=;c[]=start;inqueue[start]=;

    finish=;

    while (head<=tail){

        int u=c[head++];

        for (int v=;v<=n;v++)

         if (G[u][v]&&base[u]!=base[v]&&match[v]!=u){

                if (v==start||(match[v]>)&&(father[match[v]]>)){

                    blossomcontract(u,v);

                }else

                if (father[v]==){

                    father[v]=u;

                    if (match[v]){

                        c[++tail]=match[v];inqueue[match[v]]=;

                    }else{

                        finish=v;

                        return;

                    }

                }

         }

    }

}

void augmentpath(){

    int u,v,w;

    u=finish;

    while (u>){

        v=father[u];

        w=match[v];

        match[u]=v;

        match[v]=u;

        u=w;

    }

}

bool solve(){

    int res=;

    memset(match,,sizeof match);

    for (int i=;i<=n;i++)

     if (!match[i]){

        start=i;

        findaugmentingpath();

        if (finish) augmentpath(),res++;

     }

    for (int i=;i<=n;i++)

     if (!match[i]) return ;

    return ;

}

bool build(){

    memset(G,,sizeof G);

    int cnt=;

    for (int i=;i<=n;i++)

     if (du[i]>d[i]) return ;

    memset(p,,sizeof p);

    for (int i=;i<=m;i++){

        if (!p[e[i].u]){

            p[e[i].u]=++cnt;

            q[e[i].u]=cnt+d[e[i].u]-du[e[i].u]-;

            cnt=cnt+d[e[i].u]-du[e[i].u]-;

        }

        if (!p[e[i].v]){

            p[e[i].v]=++cnt;

            q[e[i].v]=cnt+d[e[i].v]-du[e[i].v]-;

            cnt=cnt+d[e[i].v]-du[e[i].v]-;

        }

        int k=cnt+;cnt+=;

        G[k][k-]=G[k-][k]=;

        for (int j=p[e[i].u];j<=q[e[i].u];j++) G[j][k-]=G[k-][j]=;

        for (int j=p[e[i].v];j<=q[e[i].v];j++) G[j][k]=G[k][j]=;

    }

    n=cnt;

    return ;

}

int main(){

    int Tcase=;

    int T=read();

    while (T--){

        n=read();m=read();

        printf("Case %d: ",++Tcase);

        memset(d,,sizeof d);

        for (int i=;i<=m;i++){

            e[i].u=read();e[i].v=read();

            d[e[i].u]++;d[e[i].v]++;

        }

        for (int i=;i<=n;i++) du[i]=read();

        if (build()&&solve()){

            printf("YES\n");

        }else{

            printf("NO\n");

        }

    }

    return ;

}