首页 > 代码库 > POJ1336 The K-League[最大流 公平分配问题]
POJ1336 The K-League[最大流 公平分配问题]
The K-League
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 715 | Accepted: 251 |
Description
Supporters for the professional soccer clubs participating in the K-League, formerly the Korea Professional Soccer League, hold orderly and organized cheering, as did the Red Devils, the official supporters for the Korean national soccer team during the 2002 Korea-Japan World Cup. After many games of this season have been played, the supporters may wonder whether the team S they are backing can still win the championship. In other words, can winners be assigned for the remaining games so that no team ends with more victories than S?(Two or more teams can win the championship jointly.)
You are given the current number of wins and defeats, wi and di, for every team i, 1<=i<=n, and the remaining number, ai,j, of games to be played between every pair of teams i and j, 1<=i,j<=n, where n is the number of teams. The teams are numbered 1,2,...,n. You are to find all teams that have a possibility of winning the championship. Every team has to play the same number games during the season. For simplicity, we assume that there are no draws, that is, every game has a winner and a loser.
You are given the current number of wins and defeats, wi and di, for every team i, 1<=i<=n, and the remaining number, ai,j, of games to be played between every pair of teams i and j, 1<=i,j<=n, where n is the number of teams. The teams are numbered 1,2,...,n. You are to find all teams that have a possibility of winning the championship. Every team has to play the same number games during the season. For simplicity, we assume that there are no draws, that is, every game has a winner and a loser.
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of three lines: the first line has an integer n, 1<=n<=25, that represents the number of teams in the test case; the second line contains 2n nonnegative integers w1,d1,w2,d2... each at most 100, where wi and di are the current numbers of wins and defeats for team i, respectively; the third line contains n2 nonnegative integers a1,1,a1,2,... each at most 10, where ai,j is the remaining number of games to be played between teams i and j . For all i and j, ai,j=aj,i. If i=j, then ai,j=0. The integers given in a line are delimited by one or more spaces.
Output
Print exactly one line for each test case. The line should contain all teams that have a possibility of winning the championship, in an increasing order of team numbers.
Sample Input
332 0 1 1 0 20 2 2 2 0 2 2 2 034 0 2 2 0 40 1 1 1 0 1 1 1 040 3 3 1 1 3 3 00 0 0 2 0 0 1 0 0 1 0 0 2 0 0 0
Sample Output
1 2 31 22 4
Source
Taejon 2002
公平分配模型
判断队伍i能否获胜，让i的所有比赛都获胜，其他就是把比赛的胜利分配给队伍，是他们的获胜次数<=i的获胜次数
每场比赛(i,j)一个点，s到(i,j)连容量为c[i][j]的边，(i,j)到i和j分别连INF
除i外节点j到t连 i获胜次数-win[j] 的边
注意 i获胜次数-win[j] 的边<0一定不行
//// main.cpp// poj1336//// Created by Candy on 26/11/2016.// Copyright © 2016 Candy. All rights reserved.//#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=1005,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int T,n,num,sum,win[N],los[N],s,t,c[N][N];struct edge{ int v,ne,c,f;}e[N<<1];int cnt,h[N];inline void ins(int u,int v,int c){//printf("ins %d %d %d\n",u,v,c); cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;}int tot;bool build(int x){//printf("build %d\n",tot); cnt=0; memset(h,0,sizeof(h)); for(int i=1;i<=n;i++) if(i!=x){ for(int j=i+1;j<=n;j++) if(j!=x){ int id=(i-1)*n+j; ins(s,id,c[i][j]); ins(id,num+i,INF); ins(id,num+j,INF); } ins(num+i,t,tot-win[i]); if(tot-win[i]<0) return false; } return true;}int cur[N];int vis[N],d[N],q[N],head,tail;bool bfs(){ memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); head=tail=1; q[tail++]=s;d[s]=0;vis[s]=1; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1;d[v]=d[u]+1; q[tail++]=v; if(v==t) return 1; } } } return 0;}int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) break; } } return flow;}int dinic(){ int flow=0; while(bfs()){ for(int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,INF); } return flow;}int main(int argc, const char * argv[]) { T=read(); while(T--){ n=read();s=0;t=n*n+n+1;num=n*n;sum=0; for(int i=1;i<=n;i++) win[i]=read(),los[i]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=read(),sum+=j>i?c[i][j]:0; for(int i=1;i<=n;i++){//printf("sol %d\n",i); tot=win[i]; for(int j=1;j<=n;j++) tot+=c[i][j]; if(!build(i)) continue; int tmp=dinic();//printf("dinic %d sum %d %d\n",tmp,sum,sum-tot+win[i]); if(tmp==sum-tot+win[i]) printf("%d ",i); } puts(""); } return 0;}
POJ1336 The K-League[最大流 公平分配问题]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。