hdu - 1083 - Courses

题意：有P门课程，N个学生，每门课程有一些学生选读，每个学生选读一些课程，问能否选出P个学生组成一个委员会，使得每个学生代言一门课程（他必需选读其代言的课程），每门课程都被一个学生代言(1 <= P <= 100，1 <= N <= 300) 。

——>>第一次自己想出的网络流。。。虽然是水题，但也开心死死。。。

建图：设超级源S，S到每门课程连一条边，容量为1；每门课程向其选读的学生各连一条边，容量为1；每个学生向超级汇连一条边，容量为1。

这样，只要求一次最大流，判断其是否为满流P就好。。。

#include <cstdio>  
#include <queue>  
#include <algorithm>  
#include <cstring>  
  
using namespace std;  
  
const int maxn = 400 + 10;  
const int maxm = 60800 + 10;  
const int INF = 0x3f3f3f3f;  
  
int head[maxn], nxt[maxm], ecnt, v[maxm], flow[maxm], cap[maxm];  
bool flag[maxn];  
  
struct Dinic{  
    int m, s, t;  
    int d[maxn], cur[maxn];  
    bool vis[maxn];  
  
    Dinic(){  
        memset(head, -1, sizeof(head));  
        ecnt = 0;  
    }  
  
    void addEdge(int uu, int vv, int ca){  
        v[ecnt] = vv; cap[ecnt] = ca; flow[ecnt] = 0; nxt[ecnt] = head[uu]; head[uu] = ecnt; ecnt++;  
        v[ecnt] = uu; cap[ecnt] = 0; flow[ecnt] = 0; nxt[ecnt] = head[vv]; head[vv] = ecnt; ecnt++;  
    }  
  
    bool bfs(){  
        d[s] = 0;  
        memset(vis, 0, sizeof(vis));  
        queue<int> qu;  
        qu.push(s);  
        vis[s] = 1;  
        while(!qu.empty()){  
            int u = qu.front(); qu.pop();  
            for(int e = head[u]; e != -1; e = nxt[e]){  
                if(!vis[v[e]] && cap[e] > flow[e]){  
                    d[v[e]] = d[u] + 1;  
                    vis[v[e]] = 1;  
                    qu.push(v[e]);  
                }  
            }  
        }  
        return vis[t];  
    }  
  
    int dfs(int u, int a){  
        if(u == t || a == 0) return a;  
        int f, Flow = 0;  
        for(int e = cur[u]; e != -1; e = nxt[e]){  
            cur[u] = e;  
            if(d[v[e]] == d[u] + 1 && (f = dfs(v[e], min(a, cap[e]-flow[e]))) > 0){  
                flow[e] += f;  
                flow[e^1] -= f;  
                Flow += f;  
                a -= f;  
                if(!a) break;  
            }  
        }  
        return Flow;  
    }  
  
    int Maxflow(int s, int t){  
        this->s = s;  
        this->t = t;  
        int Flow = 0;  
        while(bfs()){  
            memcpy(cur, head, sizeof(head));  
            Flow += dfs(s, INF);  
        }  
        return Flow;  
    }  
  
};  
  
int main()  
{  
    int T, P, N, S, cnt;  
    scanf("%d", &T);  
    while(T--){  
        Dinic din;  
        scanf("%d%d", &P, &N);  
        for(int i = 1; i <= P; i++){  
            din.addEdge(0, i, 1);  
            scanf("%d", &cnt);  
            for(int j = 1; j <= cnt; j++){  
                scanf("%d", &S);  
                din.addEdge(i, P+S, 1);  
            }  
        }  
        for(int i = 1; i <= N; i++) din.addEdge(P+i, P+N+1, 1);  
        if(din.Maxflow(0, P+N+1) == P) puts("YES");  
        else puts("NO");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,