C. Basic Diplomacy

C. Basic Diplomacy

网络流

/*
    https://codeforces.ml/contest/1484/problem/C  
    C. Basic Diplomacy
*/
#include<bits/stdc++.h>

int T,n,m,s,t,temp,u,v;
#define SZ(v) (int)v.size()

const int INF = 1e9;
const int MAXN = 3e5+100;
const int MAXM = 3e5 + 100;

namespace MaxFlow {
    struct Edge {
        int v, rev, f;
    };

    int n, s, t;
    int cur[MAXM], dep[MAXN], gap[MAXN];
    int flow;
    std::vector<Edge> G[MAXN];

    void add_edge(int u, int v, int f) {
        G[u].push_back({v, SZ(G[v]), f});
        G[v].push_back({u, SZ(G[u]) - 1, 0});
    }

    int dfs(int u, int lim) {
        if (u == t) return lim;
        int num = 0, f;
        for (int &i = cur[u], v; i < SZ(G[u]); ++i) {
            if (dep[v = G[u][i].v] == dep[u] - 1 && (f = G[u][i].f))
                if (G[u][i].f -= (f = dfs(v, std::min(lim - num, f))),
                        G[v][G[u][i].rev].f += f, (num += f) == lim)
                    return num;
        }
        if (!--gap[dep[u]++]) dep[s] = n + 1;
        return ++gap[dep[u]], cur[u] = 0, num;
    }

    void init(int _n) {
        n = _n;
        for (int i = 1; i <= _n; ++i) G[i].clear();
    }

    void solve(int _s, int _t) {
        s = _s, t = _t, flow = 0;
        for (int i = 0; i <= n; ++i) cur[i] = dep[i] = gap[i] = 0;
        for (gap[0] = n; dep[s] <= n; flow += dfs(s, INF));
    }
     
    void print(){
        for(int i=1;i<=m;i++){
            for(int j=0;j<G[i].size();j++){
                int v=G[i][j].v;
                if(G[v][G[i][j].rev].f>0) {printf("%d ",v-m);break;}
            }
            //puts("");
        }
        puts("");
    }
   
}

using MaxFlow::add_edge;

int main() {
    //         // 这个板子 0 点不能用，下标必须从 1 开始
    //         int n, m, s, t;
    //         scanf("%d%d", &n, &m);
    //         s = n + n + 1, t = n + n + 2;
    //         MaxFlow::init(n + n + 2);
    //         for (int i = 0, x, y; i < m; ++i) {
    //             scanf("%d%d", &x, &y);
    //             add_edge(x, y + n,1);
    // }
    // for (int i = 1; i <= n; ++i) add_edge(s, i, 1), add_edge(i + n, t, 1);
    // MaxFlow::solve(s, t);
    // printf("%d\n", MaxFlow::flow);
    // return 0;
    
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        s=n+m+1,t=s+1;
        MaxFlow::init(t);
        for(int i=1;i<=m;i++){
            scanf("%d",&temp);
            for(int j=1;j<=temp;j++){
                scanf("%d",&u);
                add_edge(i,u+m,1);
            }
            add_edge(s,i,1);
        }
        for(int i=1;i<=n;i++){
            add_edge(i+m,t,(m+1)/2);
        }
        MaxFlow::solve(s,t);
        if(MaxFlow::flow==m){
            printf("YES\n");
            MaxFlow::print();
        }
        else {
            printf("NO\n");
        }
        
    }
    //system("pause");
}

C. Basic Diplomacy

原文：https://www.cnblogs.com/zx0710/p/14588169.html