http://acm.hdu.edu.cn/showproblem.php?pid=4560
网络流好像经常搭配上二分和拆点。
n个歌手，m种歌曲流派（n<=m<=75）
我们想要安排尽可能多的演唱会。不过有以下条件——
1，每场演唱会中，每个歌手要唱不同类型的歌曲。
2，这样可能导致有些歌手去唱他不擅长的歌曲。对于任一种歌曲，被不合适唱的次数都不能超过L。
问你最多能安排多少场演唱会
想了一想发现最大流不能直接流，因为很难表示一场比赛需要M个流派的条件
发现这道题总共有三个信息，歌手，流派和比赛场次。
我们考虑二分他的比赛场次，对于场次x
源点流向每一个歌手x，x流向他不擅长的歌曲1，或者流向他擅长的歌曲1，然后不擅长的歌曲流向同一首歌的擅长的歌曲K表示最多有K个歌手可以不擅长，最后所有擅长的歌曲流向源点t，x的大小。
这需要将每一首歌曲拆成擅长的和不擅长的两个点进行建图。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; inline int read(){int now=0;register char c=getchar();for(;!isdigit(c);c=getchar()); for(;isdigit(c);now=now*10+c-'0',c=getchar());return now;} #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; const double eps = 1e-9; const int maxn = 2e5 + 10; const int maxm = 6e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; struct Dinic{ struct Edge{ int from,to,cap,flow,nxt; Edge() {} Edge(int u,int v,int c,int f,int n):from(u),to(v),cap(c),flow(f),nxt(n) {} }edge[maxm]; int n,s,t,E,head[maxn]; bool vis[maxn]; int d[maxn],cur[maxn]; inline void AddEdge(int f,int t,int c){ edge[++E] = Edge(f,t,c,0,head[f]); head[f] = E; edge[++E] = Edge(t,f,0,0,head[t]); head[t] = E; } inline void Init(int n,int s,int t){ this -> n = n; E = -1; this -> s = s; head[s] = -1; this -> t = t; head[t] = -1; for(int i = 0 ; i <= n ; i ++) head[i] = -1; } inline bool BFS(){ memset(vis,0,sizeof(vis)); queue<int>Q; d[s] = 0;vis[s] = 1; for(Q.push(s);!Q.empty();){ int x = Q.front(); Q.pop(); for(int nxt,i = head[x];~i;i = nxt){ Edge &e = edge[i]; nxt = e.nxt; if(vis[e.to] || e.cap <= e.flow) continue; vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } return vis[t]; } inline int DFS(const int &x,int a){ if(x == t || a == 0) return a; int flow = 0,f,nxt; for(int &i = cur[x]; ~i; i = nxt){ Edge &e = edge[i]; nxt = e.nxt; if(d[x] + 1 != d[e.to]) continue; f = DFS(e.to,min(a,e.cap - e.flow)); if(f <= 0) continue; e.flow += f; edge[i ^ 1].flow -= f; flow += f; a -= f; if(!a) break; } return flow; } inline int maxFlow(){return maxFlow(s,t);} inline int maxFlow(int s,int t){ int flow = 0; for(;BFS();){ for(int i = 0 ;i <= n ; i ++) cur[i] = head[i]; flow += DFS(s,INF); } return flow; } }g; int N,M,L,K; bool MAP[100][100]; bool check(int x){ int s = 0 ,t = N + M * 2 + 1; g.Init(t,s,t); For(i,1,N) g.AddEdge(s,i,x); For(i,1,N){ For(j,1,M){ if(MAP[i][j]){ g.AddEdge(i,j + N,1); }else{ g.AddEdge(i,j + N + M,1); } } } For(i,1,M) g.AddEdge(i + N,t,x); For(i,1,M) g.AddEdge(i + N + M,i + N,K); return ((LL)g.maxFlow() >= ((LL)x * N)); } int solve(){ int l = 0,r = INF; int ans = 0; while(l <= r){ int m = (l + r) >> 1; if(check(m)){ ans = m; l = m + 1; }else{ r = m - 1; } } return ans; } int main() { int T; Sca(T); int CASE = 1; while(T--){ Sca2(N,M); Sca2(L,K); Mem(MAP,0); For(i,1,L){ int x,y; Sca2(x,y); MAP[x][y] = 1; } printf("Case %d: ",CASE++); Pri(solve()); } #ifdef VSCode system("pause"); #endif return 0; }