首页 > 代码库 > BZOJ 1532 [POI2005]Kos-Dicing(二分+最大流判断)
BZOJ 1532 [POI2005]Kos-Dicing(二分+最大流判断)
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1532
【题目大意】
n个人,给出m场比赛,求出胜出的人最少赢的场次。
【题解】
我们发现答案具有单调性,因此我们可以二分检验,
建立源点向每个人引流限定的胜利场次,每个人向每场比赛引流1,
每场比赛向汇点引流1,表示比赛获胜者只能有一人,
如果最大流等于比赛场次,那意味着该答案可行。
【代码】
#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int INF=0x3f3f3f3f;const int MAX_V=20010;struct edge{int to,cap,rev;}; vector<edge> G[MAX_V];int level[MAX_V],iter[MAX_V];void add_edge(int from,int to,int cap){ G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size()-1});}void bfs(int s){ memset(level,-1,sizeof(level)); queue<int> que; level[s]=0; que.push(s); while(!que.empty()){ int v=que.front(); que.pop(); for(int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } }}int dfs(int v,int t,int f){ if(v==t)return f; for(int &i=iter[v];i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[v]<level[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } }return 0;}int max_flow(int s,int t){ int flow=0; for(;;){ bfs(s); if(level[t]<0)return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF))>0){ flow+=f; } }}const int MAX_M=10010;const int MAX_N=10010;int N,M;int e[MAX_M][2];bool check(int x){ int s=0,t=N+M+1; for(int i=0;i<=t;i++)G[i].clear(); for(int i=1;i<=N;i++)add_edge(s,i,x); for(int i=1;i<=M;i++){ add_edge(e[i][0],i+N,1),add_edge(e[i][1],i+N,1); add_edge(i+N,t,1); }return max_flow(s,t)==M;}int main(){ while(~scanf("%d%d",&N,&M)){ for(int i=1;i<=M;i++)scanf("%d%d",&e[i][0],&e[i][1]); int l=1,r=M,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; }printf("%d\n",ans); }return 0;}
BZOJ 1532 [POI2005]Kos-Dicing(二分+最大流判断)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。