I题题解

这道题和HDU 3551是一样的。
关键在拆点建图上
把点v拆成d[v]个点。同时将每条边拆成2个点分别为。将相连。同时将与拆成的个点连边，将与拆成的个点连边。
如题目中样例的第三组数据：

3 2
1 1 2
1 3
2 3

第1个点拆成1个点，编号为1。
第2个点拆成1个点，编号为2。
第3个点拆成2个点，编号分别为3，4
第1条边拆成两个点，编号为5，6。（5，6）（5，1）（6，3）（6，4）连边。
第2条边拆成两个点，编号为7，8。（7，8）（7，2）（8，3）（8，4）连边。
注意这里的边是无向边。
建图之后跑一般图匹配。如果是完全匹配输出“yes”，否则输出“no”

为什么这样可行？

将每个点拆成若干个“度”，每一个“度”都与一条边相连。而每一条边可以提供2个“度”。如果可行，那么每一个“度”都有一条边给它提供。如果存在一条边不需要给其他点提供“度”，那么这条边本身拆成的2个点形成匹配。所以若可行，则一定是完全匹配。
在建图过程中，可以看到，每一个点拆成的“度”，不存在与另一个点拆成的“度”之间的边。现在假设建完图后可以完全匹配。那么每一组匹配只有两种情况：1. 某个点拆成的某个“度”与一条边拆成的其中一个点匹配。2.一条边拆成的2个点的匹配。又因为是完全匹配，所以每个“度”都有某一条边拆成的点与之匹配。所以若是完全匹配，则一定可行。

代码：
这个代码是直接把kuangbin的一般图匹配模板改了一下，只改了CreatGraph()函数和PrintMatch()函数，所以只看这两个函数就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1000+20;
const int INF=0x3f3f3f3f;
const LL MOD=998244353;
int N,M;
int n,m;
int d[MAX_N];
bool Graph[MAX_N][MAX_N];
int Match[MAX_N];
bool InQueue[MAX_N],InPath[MAX_N],InBlossom[MAX_N];
int Head,Tail;
int Queue[MAX_N];
int Start,Finish;
int NewBase;
int Father[MAX_N],Base[MAX_N];
int Count;
vector<int>V[MAX_N];
void CreatGraph(){
    int u,v;

    memset(Graph,false,sizeof(Graph));
    int tot=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
        V[i].clear();
        for(int j=1;j<=d[i];j++)V[i].push_back(tot++);
    }

    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        int x=tot++,y=tot++;
        Graph[x][y]=Graph[y][x]=1;
        for(int j=0;j<V[u].size();j++){
            Graph[x][V[u][j]]=Graph[V[u][j]][x]=1;
        }
        for(int j=0;j<V[v].size();j++){
            Graph[y][V[v][j]]=Graph[V[v][j]][y]=1;
        }
    }
    N=tot-1;
}
void Push(int u){
    Queue[Tail]=u;
    Tail++;
    InQueue[u]=true;
}
int Pop(){
    int res=Queue[Head];
    Head++;
    return res;
}
int FindCommonAncestor(int u,int v){
    memset(InPath,false,sizeof(InPath));
    while(1){
        u=Base[u];
        InPath[u]=1;
        if(u==Start)break;
        u=Father[Match[u]];
    }
    while(1){
        v=Base[v];
        if(InPath[v])break;
        v=Father[Match[v]];
    }
    return v;
}
void ResetTrace(int u){
    int v;
    while(Base[u]!=NewBase){
        v=Match[u];
        InBlossom[Base[u]]=InBlossom[Base[v]]=1;
        u=Father[v];
        if(Base[u]!=NewBase)Father[u]=v;
    }
}
void BloosomContract(int u,int v){
    NewBase=FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u]!=NewBase)Father[u]=v;
    if(Base[v]!=NewBase)Father[v]=u;
    for(int tu=1;tu<=N;tu++){
        if(InBlossom[Base[tu]]){
            Base[tu]=NewBase;
            if(!InQueue[tu])Push(tu);
        }
    }
}
void FindAugmentingPath(){
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i=1;i<=N;i++){
        Base[i]=i;
    }
    Head=Tail=1;
    Push(Start);
    Finish=0;
    while(Head<Tail){
        int u=Pop();
        for(int v=1;v<=N;v++){
            if(Graph[u][v]&&(Base[u]!=Base[v])&&(Match[u]!=v)){
                if((v==Start)||((Match[v]>0)&&Father[Match[v]]>0))BloosomContract(u,v);
                else if(Father[v]==0){
                    Father[v]=u;
                    if(Match[v]>0)Push(Match[v]);
                    else{
                        Finish=v;
                        return;
                    }

                }
            }
        }
    }
}
void AugmentPath(){
    int u,v,w;
    u=Finish;
    while(u>0){
        v=Father[u];
        w=Match[v];
        Match[v]=u;
        Match[u]=v;
        u=w;
    }
}
void Edmonds(){
    memset(Match,0,sizeof(Match));
    for(int u=1;u<=N;u++){
        if(Match[u]==0){
            Start=u;
            FindAugmentingPath();
            if(Finish>0)AugmentPath();
        }
    }
}
void PrintMatch(){
    Count=0;
    for(int u=1;u<=N;u++){
        if(Match[u]>0)Count++;
    }
    if(Count==N)printf("Yes\n");
    else printf("No\n");
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);
    while(scanf("%d%d",&n,&m)==2){
        CreatGraph();
        Edmonds();
        PrintMatch();
    }

}