【题意】
有n个队伍进行比赛，每场比赛，恰好有一支队伍取胜、一支队伍败。每个队伍需要打的比赛场数相同，给你每个队伍目前已经赢得场数和输得场数，再给你一个矩阵，第 i 行第 j 列 表示队伍 i 和队伍 j 还需要打的比赛数，问你哪些队伍有可能获得冠军（胜场最多的即为冠军，可以并列）。
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, . . . , wn, dn,
each at most 100, where wi and di are the current numbers of wins and defeats for team i, respectively;
the third line contains n
2 nonnegative integers a1,1, a1,2, . . . , a1,n, a2,1, a2,2, . . . , a2,n, · · · , an,1, an,2, . . . , an,n,
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 is equal to 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
3
3
2 0 1 1 0 2
0 2 2 2 0 2 2 2 0
3
4 0 2 2 0 4
0 1 1 1 0 1 1 1 0
4
0 3 3 1 1 3 3 0
0 0 0 2 0 0 1 0 0 1 0 0 2 0 0 0
Sample Output
1 2 3
1 2
2 4
【分析】
枚举判断每个队伍是否可以是冠军。
然后贪心的思想，想让他在接下来的比赛中全部获胜，接下来只用判断其他队伍的比赛是否可以相互制约，使得枚举的是总冠军。
st->(u,v)，表示比赛，流量为比场数。
(u,v)->u (u,v)->v 流量为INF
u->ed 流量为tot-w[u] ，tot为枚举的那个的现在计算出的胜利场数，如果他是冠军，那么其他队伍的胜利场数不能超过他。
跑最大流，然后判断st->xxx 是否满流。
这题跟公平分配问题是相似的模型。
把每场比赛看成“任务”，每支队伍看成“处理器”，tot是制约（相当于我们二分的答案）。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 30
#define Mn 1010
#define INF 0xfffffff struct node
{
int x,y,f,o,next;
}t[Mn*];
int len,first[Mn]; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y,int f)
{
if(f<=) return;
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} int w[Maxn],d[Maxn],a[Maxn][Maxn];
int n; void init()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&w[i],&d[i]);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
{
a[i][]=;
for(int j=;j<=n;j++) a[i][]+=a[i][j];
}
} int dis[Mn],st,ed;
queue<int > q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
q.pop();
}
if(dis[ed]==-) return ;
return ;
} int ffind(int x,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
}
if(now==flow) break;
}
if(now==) dis[x]=-;
return now;
} int max_flow()
{
int ans=;
while(bfs())
{
ans+=ffind(st,INF);
}
return ans;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
bool op=;
for(int i=;i<=n;i++)
{
int tot=a[i][]+w[i],cnt,sum=;
len=;
memset(first,,sizeof(first));
st=n+,ed=st+,cnt=ed;
bool ok=;
for(int j=;j<=n;j++) if(j!=i)
{
ins(j,ed,tot-w[j]);
if(tot-w[j]<) ok=;
}
for(int j=;j<=n;j++) if(j!=i)
for(int k=j+;k<=n;k++) if(k!=i)
{
sum+=a[j][k];
ins(st,++cnt,a[j][k]),ins(cnt,j,INF),ins(cnt,k,INF);
}
int x=max_flow();
if(x!=sum) ok=;
if(ok)
{
if(op) printf(" ");
op=;
printf("%d",i);
}
}
// if(T)
printf("\n");
}
return ;
}
输出文件末不输出空行是WA，行末有空格是PE，也是。。
2016-11-04 07:47:58