hdu 4560 拆点最大流 ***

题意：

2013年一开始，一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说，现在，你成为了这档节目的总导演，你的任务很简单，安排每一期节目的内容。

现在有N个歌手，M种歌曲流派（Rock，Pop之类），每个歌手都有自己擅长的流派领域，这些资料都已整理好。你的工作是，安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场，为了提高收视率，每个人演唱的歌曲类型不能相同，即便一些歌手要被迫选择一些他们不擅长的。同时，为了展现全面性，在不同的演唱比赛上，每个歌手都会安排不同的歌曲流派。

但是问题是，对于任何一个歌曲流派的歌迷，如果超过K个不擅长的歌手演唱了这种歌曲，他们就会表示不满，比如，发一些宣泄不满的帖子微博，为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关，在这个前提下，你可以任意安排尽可能多的比赛场次。

链接：点我

online_judge写错了，wa了好多发

N个歌手编号为1~N

M种歌曲，拆点。编号分别为N+1~N+M,N+M+1~N+2*M

源点为0,汇点为N+2*M+1 总共N+2*M+2个点。

N+i 和 N+M+i 之间连权值为K的边，作为限制。

对于i, j 如果i对j擅长，那么连边 i -> N+M+j

否则连边 i -> N+j 这样就可以限制了。

然后是二分答案。

0~(1~N)之间，连边 mid .

(N+M+1~N+2*M)与N+2*M+1之间也连边mid

然后判断mid*N和最大流是不是相当。

然后就是最大流模板题了。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define mOD 1000000007
 10 #define pb(a) push_back(a)
 11 const int InF=0x3f3f3f3f;
 12 const double eps=1e-5;
 13 typedef long long ll;
 14 #define cl(a) memset(a,0,sizeof(a))
 15 #define ts printf("*****
");
 16 const int MAXN=1010;
 17 int n,m,tt,cnt;
 18 int maze[MAXN][MAXN];
 19 int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];
 20 int flow[MAXN][MAXN];//存最大流的容量
 21 int sap(int start,int end,int nodenum)
 22 {
 23 memset(cur,0,sizeof(cur));
 24 memset(dis,0,sizeof(dis));
 25 memset(gap,0,sizeof(gap));
 26 memset(flow,0,sizeof(flow));
 27 int u=pre[start]=start,maxflow=0,aug=-1;
 28 gap[0]=nodenum;
 29 while(dis[start]<nodenum)
 30 {
 31 loop:
 32 for(int v=cur[u];v<nodenum;v++)
 33 if(maze[u][v]-flow[u][v] && dis[u]==dis[v]+1)
 34 {
 35 if(aug==-1 || aug>maze[u][v]-flow[u][v])aug=maze[u][v]-flow[u][v];
 36 pre[v]=u;
 37 u=cur[u]=v;
 38 if(v==end)
 39 {
 40 maxflow+=aug;
 41 for(u=pre[u];v!=start;v=u,u=pre[u])
 42 {
 43 flow[u][v]+=aug;
 44 flow[v][u]-=aug;
 45 }
 46 aug=-1;
 47 }
 48 goto loop;
 49 }
 50 int mindis=nodenum-1;
 51 for(int v=0;v<nodenum;v++)
 52 if(maze[u][v]-flow[u][v]&&mindis>dis[v])
 53 {
 54 cur[u]=v;
 55 mindis=dis[v];
 56 }
 57 if((--gap[dis[u]])==0)break;
 58 gap[dis[u]=mindis+1]++;
 59 u=pre[u];
 60 }
 61 return maxflow;
 62 }
 63 bool check(int mid)
 64 {
 65     for(int i=1;i<=n;i++)
 66     {
 67         maze[0][i]=mid;
 68     }
 69     for(int i=n+m+1;i<=n+2*m;i++)maze[i][n+2*m+1]=mid;
 70     if(sap(0,n+2*m+1,n+2*m+2)==mid*n)   return 1;
 71     else
 72         return 0;
 73 }
 74 int used[MAXN][MAXN];
 75 int main()
 76 {
 77     int i,j,k;
 78     int ca=1;
 79     #ifndef ONLINE_JUDGE
 80     freopen("1.in","r",stdin);
 81     #endif
 82     scanf("%d",&tt);
 83     int l;
 84     while(tt--)
 85     {
 86         scanf("%d%d%d%d",&n,&m,&l,&k);
 87         cl(used);
 88         cl(maze);
 89         int q,p;
 90         for(i=1;i<=l;i++)
 91         {
 92             scanf("%d%d",&q,&p);
 93             used[q][p]=1;
 94         }
 95 
 96         for(i=n+1;i<=n+m;i++)maze[i][i+m]=k;
 97         for(int i=1;i<=n;i++)
 98             for(int j=1;j<=m;j++)
 99             {
100                 if(used[i][j])
101                 {
102                     maze[i][j+n+m]=1;
103                 }
104                 else maze[i][j+n]=1;
105             }
106         int l=0,r=m;
107         int ans=0;
108          while(l<=r)
109         {
110             int mid=(l+r)>>1;
111             if(check(mid))
112             {
113                 ans=mid;
114                 l=mid+1;
115             }
116             else r=mid-1;
117         }
118         printf("Case %d: %d
",ca++,ans);
119     }
120 }