I 1 or 2(挑选边使度数满足)

题：https://ac.nowcoder.com/acm/contest/5666/I

题意：挑选边，让点的度数满足d数组,1<=du[i]<=2

分析：di为1时就是普通的一般图匹配，而考虑di为2的情况，将度为2的点拆成2个点，同时将边也当作点来拆成2个点，连u-e，u‘-e，e-e’，v-e‘，v’-e‘（这里假设u和v的di为2，di为1的点自然不用拆）；

　　　然后套一般图最大匹配，在最大匹配中，要么选择e-e'表示不选这条边，最大匹配+1；要么就选e- ，e‘- 表示选择这条边，最大匹配+2。

　　　求出的最大匹配中，不管怎么选每条边至少有1贡献，那么我们不妨每条边都减去1，得到的贡献是0或1代表选与不选，而总和的最大匹配的2倍就是度数了（一匹配=2度数）

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

void pn(){
    puts("No");
}
void py(){
    puts("Yes");
}
const int M=505;
int n, m;
int du[M];
struct mf{
    int vis[M],par[M],orig[M],match[M],aux[M],tot,n;
    vector<int> g[M];
    queue<int> Q;
    void addedge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void init(int _n){
        n=_n;
        tot=0;
        for (int i=0;i<=n;i++){
            g[i].clear();
            match[i]=aux[i]=par[i]=0;
        }
    }
    void augment(int u,int v){
        int pv=v,nv;
        do{
            pv=par[v];
            nv=match[pv];
            match[v]=pv;
            match[pv]=v;
            v = nv;
        }while(u!=pv);
    }
    int lca(int v,int w){
        ++tot;
        while(true){
            if(v){
                if(aux[v] == tot) return v;
                aux[v]=tot;
                v=orig[par[match[v]]];
            }
            swap(v, w);
        }
    }
    void blossom(int v, int w, int a) {
        while (orig[v]!=a){
            par[v]=w;
            w=match[v];
            if(vis[w] == 1) Q.push(w),vis[w] = 0;
            orig[v]=orig[w]=a;
            v=par[w];
        }
    }
    bool bfs(int u){
        fill(vis + 1, vis + 1 + n, -1);
        iota(orig + 1, orig + n + 1, 1);
        Q = queue<int>();
        Q.push(u);
        vis[u] = 0;
        while (!Q.empty()) {
            int v = Q.front();
            Q.pop();
            for (int x : g[v]) {
                if (vis[x] == -1) {
                    par[x] = v;
                    vis[x] = 1;
                    if (!match[x]) return augment(u, x), true;
                    Q.push(match[x]);
                    vis[match[x]] = 0;
                } else if (vis[x] == 0 && orig[v] != orig[x]) {
                    int a = lca(orig[v], orig[x]);
                    blossom(x, v, a);
                    blossom(v, x, a);
                }
            }
        }
        return false;
    }
    int Match() {
        int ans = 0;
        // find random matching (not necessary, constant improvement)
        vector<int> V(n - 1);
        iota(V.begin(),V.end(), 1);
        shuffle(V.begin(),V.end(),mt19937(61471));
        for (auto x:V)
            if (!match[x]) {
                for (auto y:g[x])
                if (!match[y]) {
                    match[x]=y,match[y]=x;
                    ++ans;
                    break;
                }
            }
        for (int i = 1; i <= n; ++i)
            if (!match[i] && bfs(i)) ++ans;
        return ans;
    }
}mf;
int main(){
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF){
        mf.init(500);

        int deg=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&du[i]);
            deg+=du[i];
        }
        int nowi=102;
        for(int u,v,i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            mf.addedge(nowi,nowi+1);
            for(int j=0;j<du[u];j++)
                mf.addedge(2*u+j,nowi);
            for(int j=0;j<du[v];j++)
                mf.addedge(nowi+1,2*v+j);
            nowi+=2;
        }
        int ans=mf.Match();
        if(deg==ans*2-m*2)
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}

View Code

原文链接: https://www.cnblogs.com/starve/p/13321786.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367180

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

I 1 or 2(挑选边使度数满足)

相关推荐