题意：和HDU3081一样的题意，只不过多了一个条件，每个女孩除了能选自己喜欢的男生之外，还能选不超过K个自己不喜欢的男生，问游戏最多能进行几轮
思路：除了选喜欢的，还能选任意K个不喜欢的，怎么建图呢？一开始我想每个女孩连喜欢的男孩，而且选K个不喜欢的男孩也连边，可是这K个要怎么确定呢？这种显然是行不通的，然后我想每个女孩和不喜欢的男孩连边，男孩和汇点连一条容量为K的边，那么其实也显然不对了。建图思路很巧妙，将每个女孩拆成两个点，中间连一条容量为K的边
假设当前我们二分轮数为limit, 源点s编号0,女孩i分成两个点i和i+n编号(编号i的点用来连接该女孩喜欢的男孩,编号为i+n的点用来连接该女孩不喜欢的男孩), 男孩编号为2n+1到2n+n, 汇点t编号为3n+1.
首先源点s到第i个女孩有边(s, i, limit)
第i个女孩的i点到i+n点有边(i, i+n, k)
如果第i个女孩可以选男孩j,那么有边(i, j, 1). 否则有边(i+n, j, 1)
每个男孩j到汇点t有边(j, t, limit)
最终看max_flow 是否== limit*n 即可.
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
using namespace std;
#define maxn 250*3+10
#define INF 1<<29
#define LL long long
int cas=1,T;
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int n,m;
struct Dinic
{
// int n,m;
int s,t;
vector<Edge>edges; //边数的两倍
vector<int> G[maxn]; //邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; //BFS使用
int d[maxn]; //从起点到i的距离
int cur[maxn]; //当前弧下标
void init()
{
for (int i=0;i<=n*3+1;i++)
G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0)); //反向弧
int mm=edges.size();
G[from].push_back(mm-2);
G[to].push_back(mm-1);
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(s);
d[s]=0;
vis[s]=1;
while (!q.empty())
{
int x = q.front();q.pop();
for (int i = 0;i<G[x].size();i++)
{
Edge &e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow)
{
vis[e.to]=1;
d[e.to] = d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if (x==t || a==0)
return a;
int flow = 0,f;
for(int &i=cur[x];i<G[x].size();i++)
{
Edge &e = edges[G[x][i]];
if (d[x]+1 == d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if (a==0)
break;
}
}
return flow;
}
int Maxflow(int s,int t)
{
this->s=s;
this->t=t;
int flow = 0;
while (BFS())
{
memset(cur,0,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}
}dc;
int pre[maxn];
int dis[maxn][maxn];
int Find(int x)
{
return pre[x]==-1?x:pre[x]=Find(pre[x]);
}
bool solve(int t,int k)
{
dc.init();
for (int i = 1;i<=n;i++)
{
dc.AddEdge(0,i,t); //每个女孩i'和源点连边
dc.AddEdge(i,i+n,k); //女孩的两个拆点连一条容量为k的边
dc.AddEdge(n*2+i,n*3+1,t); //每个男孩和汇点n*3+1连边
for (int j = 1;j<=n;j++)
if (dis[i][j])
dc.AddEdge(i,n*2+j,1); //女孩i'和喜欢的男孩连边，容量为1
else
dc.AddEdge(i+n,n*2+j,1); //女孩i''和不喜欢的男孩连边，容量为1
}
return dc.Maxflow(0,n*3+1)==t*n;
}
int main()
{
scanf("%d",&T);
while (T--)
{
int f,kk;
memset(dis,0,sizeof(dis));
memset(pre,-1,sizeof(pre));
scanf("%d%d%d%d",&n,&m,&kk,&f);
for (int i = 1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
dis[u][v]=1;
}
for (int i = 1;i<=f;i++)
{
int u,v;
scanf("%d%d",&u,&v);
int uu = Find(u);
int vv = Find(v);
if (uu!=vv)
pre[uu]=vv;
}
for (int i = 1;i<=n;i++)
for (int j = i+1;j<=n;j++)
if (Find(i)==Find(j))
for (int k=1;k<=n;k++)
{
dis[i][k]=dis[j][k]=(dis[i][k] || dis[j][k]);
}
int l = 0;
int r = n;
while (l<=r)
{
int mid = (l+r)/2;
if (solve(mid,kk))
l = mid+1;
else
r=mid-1;
}
printf("%d\n",r);
}
}
Description
Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the ever game of play-house . What a happy time as so many friends play together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.
Now, there are 2n kids, n boys numbered from 1 to n, and n girls numbered from 1 to n. As you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl X can also choose boy Z to be her boyfriend when her friend, girl Y has not quarreled with him. Furthermore, the friendship is mutual, which means a and c are friends provided that a and b are friends and b and c are friend.
Once every girl finds their boyfriends they will start a new round of this game―marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on. On the other hand, in order to play more times of marriage match, every girl can accept any K boys. If a girl chooses a boy, the boy must accept her unconditionally whether they had quarreled before or not.
Now, here is the question for you, how many rounds can these 2n kids totally play this game?
Input
There are several test cases. First is an integer T, means the number of test cases.
Each test case starts with three integer n, m, K and f in a line (3<=n<=250, 0<m<n*n, 0<=f<n). n means there are 2*n children, n girls(number from 1 to n) and n boys(number from 1 to n).
Then m lines follow. Each line contains two numbers a and b, means girl a and boy b had never quarreled with each other.
Then f lines follow. Each line contains two numbers c and d, means girl c and girl d are good friends.
Output
For each case, output a number in one line. The maximal number of Marriage Match the children can play.
Sample Input
1 4 5 1 2 1 1 2 3 3 2 4 2 4 4 1 4 2 3
Sample Output
3