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;  
}