LA2531TheK-League最大流

LA 2531

题意：有n个队伍比赛，给出n个队伍赢的次数和输的次数，然后再输入每个队伍还需要的比赛次数，确定所有可能得冠军的球队（获胜场数最多的得冠军，可以并列）

思路：假设a可以拿冠军，先求出a获胜的总次数tot，把每两个队伍的比赛（u，v）看成节点，从源点S连接一条弧到比赛节点，容量为比赛次数（注意排除0次比赛），然后把比赛（u，v）分别连接一条弧到到u，v，容量为 tot - win(u)和 tot - win(v)，然后把每个队伍节点连接到汇点T，容量无限大，再求最大流，如果S出发的每条弧流量的是满的，说明在a在剩下比赛的全胜的情况下，其他的队伍获胜次数不超过 tot 的情况下，比赛可以打完，a可以拿冠军，否则在限制其他队伍获胜次数下比赛打不完，a不能拿冠军。

#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000;
const int inf=1e9;
struct Edge
{
	int from,to,cap,flow;
};
struct Dinic
{
	int n,m,s,t;
	vectoredges;
	vectorG[maxn];
	bool vis[maxn];
	int d[maxn],cur[maxn];
	void init(int n)
	{
		this->n=n;
		for(int i=0;iQ;
		Q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!Q.empty())
		{
			int x=Q.front();Q.pop();
			for(int i=0;ie.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];i0)
			{
				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);
		}
	}
	int check()
	{
		int flag=1;
		for(int i=0;iedges[G[0][i]].flow)
		flag=0;
		return flag;
	}
}solver;
int win[30],lose[30],cont[30][30];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		vectorans;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d%d",&win[i],&lose[i]);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&cont[i][j]);
		for(int i=1;i<=n;i++)
		{
			int tot=0;
			for(int j=1;j<=n;j++)
			tot+=cont[i][j];
			tot+=win[i];
			int flag=1;
			for(int j=1;j<=n;j++)
			if(j!=i&&tot-win[j]<0)//已经有队伍获胜次数超过了tot，i不能拿冠军 
			flag=0;
			if(!flag)
			continue;
			solver.init(maxn);
			int res=n;
			for(int j=1;j