題意:

我是歌手

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 287 Accepted Submission(s): 97


Problem Description 2013年一開始，一檔音樂節目“我是歌手”就驚艷了大家一回。閑話少說，現在，你成為了這檔節目的總導演，你的任務很簡單，安排每一期節目的內容。

現在有N個歌手，M種歌曲流派（Rock，Pop之類），每個歌手都有自己擅長的流派領域，這些資料都已整理好。你的工作是，安排盡可能多場的演唱比賽。每一場比賽所有歌手都必須上場，為了提高收視率，每個人演唱的歌曲類型不能相同，即便一些歌手要被迫選擇一些他們不擅長的。同時，為了展現全面性，在不同的演唱比賽上，每個歌手都會安排不同的歌曲流派。

但是問題是，對于任何一個歌曲流派的歌迷，如果超過K個不擅長的歌手演唱了這種歌曲，他們就會表示不滿，比如，發一些宣泄不滿的帖子微博，為了表示觀點挑起事端等等。你當然不希望這些事情與你的節目有關，在這個前提下，你可以任意安排盡可能多的比賽場次。
Input 輸入第一行為T，表示有T組測試數據。
每組數據以四個數字N，M，L, K開始。L表示有L組擅長關系，接下來的L行，每一行有兩個數字Ai，Bi，表示歌手Ai擅長Bi類型的歌曲。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N <= M <= 74, 0 <= K <= N
3. 0 <= L <= N*M
4. 1 <= Ai <= N, 1 <= Bi <= M, 相同關系不會重復出現
Output 對每組數據，先輸出為第幾組數據，然后輸出最多比賽場次。
Sample Input 3 1 1 1 0 1 1 1 3 0 1 3 3 5 1 1 1 1 2 2 2 2 3 3 1
Sample Output Case 1: 1 Case 2: 3 Case 3: 2Hint 對第三組樣例，可以如此安排： 第一場三位歌手分別演唱（2,3,1）類型的歌曲，第二場分別演唱（1,2,3）。 這樣只有類型3被不擅長的歌手演唱過1次，挑剔的歌迷觀眾還可以接受。 思路:沒話說,看完第一反應就是個二分最大流,關鍵是在建圖,說下建圖吧.自己弱渣,建圖建了4種才ac...設立超級遠點和終點 s,t.s連接每一個人,流量是當前二分的 mid.然后連接 數據中給的人和歌曲類型,流量為1.每種類型連接t流量是mid.然后把每個歌曲類型k在拆出來一個點k'枚舉每個人,如果當前這個人沒連接k ,那么連接k'流量1每個k'連接k,流量是輸入的那個K然后跑最大流,如果 ans >= mid * N,那么mid = low + 1............. #include<stdio.h> #include<string.h> #include<queue>#define N_node 1000 #define N_edge 1000000 #define INF 1000000000 using namespace std;typedef struct {int to ,cost ,next; }STAR;typedef struct {int x ,t; }DEP;typedef struct {int a ,b; }EDGE;STAR E[N_edge]; EDGE edge[N_edge]; DEP xin ,tou; int list[N_node] ,tot; int list2[N_node]; int deep[N_node]; int mark[N_node][N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }int minn(int x, int y) {return x < y ? x : y; }bool bfs_deep(int s ,int t ,int n) {queue<DEP>q;xin.x = s;xin.t = 0;memset(deep ,255 ,sizeof(deep));deep[s] = 0;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){xin.x = E[k].to;xin.t = tou.t + 1;if(deep[xin.x] != -1 || !E[k].cost)continue;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0; i <= n ;i ++)list2[i] = list[i];return deep[t] != -1; } int dfs_flow(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = list2[s] ;k ;k = E[k].next){int to = E[k].to;int c = E[k].cost;list2[s] = k;if(deep[to] != deep[s] + 1 || !E[k].cost) continue;int tmp = dfs_flow(to ,t ,minn(c ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(nowflow == flow) break;}if(!nowflow) deep[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int ans = 0;while(bfs_deep(s ,t ,n)){ans += dfs_flow(s ,t ,INF);}return ans; }bool ok(int mid ,int L ,int K ,int N ,int M) { memset(list ,0 ,sizeof(list));tot = 1;int s = 0 ,t = N + M + M + 1 ,i;for(i = 1 ;i <= N ;i ++)add(s ,i ,mid);for(i = 1 ;i <= M ;i ++){add(i + N ,t ,mid);add(i + N + M ,i + N ,K);}for(i = 1 ;i <= L ;i ++)add(edge[i].a ,edge[i].b + N,1);for(i = 1 ;i <= N ;i ++)for(int j = 1 ;j <= M ;j ++)if(!mark[i][j])add(i ,j + N + M ,1);return DINIC(s ,t ,t) >= mid * N; }int main () {int N ,M ,L ,K;int i ,j ,a ,b;int low ,mid ,up;int t ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d %d %d" ,&N ,&M ,&L ,&K);memset(mark ,0 ,sizeof(mark));for(i = 1 ;i <= L ;i ++){scanf("%d %d" ,&edge[i].a ,&edge[i].b);mark[edge[i].a][edge[i].b] = 1;}low = 0 ,up = M;int ans = 0;while(low <= up){mid = (low + up) >> 1;if(ok(mid ,L ,K ,N ,M)){ans = mid;low = mid + 1;}elseup = mid - 1;}printf("Case %d: %d\n" ,cas ++ ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4560 不错的建图,二分最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。