hdu4560 不错的建图,二分最大流

2023-08-26 22:50:40

题意:

我是歌手

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: 2

Hint

对第三组样例，可以如此安排：
第一场三位歌手分别演唱（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;

         }

         else

         up = mid - 1;

      }

      printf("Case %d: %d\n" ,cas ++ ,ans);

   }

   return 0;

}

码农公寓

题意:

我是歌手

相关文章