首页 > 代码库 > SGU326_Perspective

SGU326_Perspective

2024-07-13 03:54:11   215人阅读

NBA打比赛。所有的比赛被分为多个团队。有的比赛是团内的，有的是与团外的队伍打的。

给出团内每个队伍已得分，以及总共有多少场比赛，还有团内所有队伍之间有多少场比赛？

问1队是否可能是分数最高的一个队伍。（题目没说是否唯一最高，枚举题意得知不是唯一）

又是一个竞赛图的最大流。团内的比赛，如果有一个队伍是1队，那么安排结果1队胜利，另一队伍失败。

对于所有与外团的比赛，与1队有关的都胜利，否则失败。

接下来建图，我们做完前面的工作后，分别统计所有的队伍得分，1队分数减去x队的分数就是x队在所有的团内赛中最多能够胜利的场数。

模型就出来了，源点->队伍->比赛->汇点，最终我们只要判断所有比赛的出边是否满流，即所有的比赛能否安排得下即可。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 5550#define maxm 55550using namespace std;int next[maxm],to[maxm],c[maxm],first[maxn],edge=-1;int score[maxn],test[maxn],tag[maxn],TAG=520;bool can[maxn];int a[222][222],node=-1,d[maxn];int Q[maxn],bot,top;int alltest=0,ans,n,m,s,t;int addnode(){    first[++node]=-1;    return node;}void addedge(int U,int V,int W){    edge++;    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){    Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,can[t]=false;    while (bot<=top)    {        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])            if (c[i^1]>0 && tag[to[i]]!=TAG)            {                tag[to[i]]=TAG,can[to[i]]=false;                d[to[i]]=d[cur]+1,Q[++top]=to[i];                if (to[i]==s) return true;            }    }    return false;}int dfs(int cur,int num){    if (cur==t) return num;    int tmp=num,k;    for (int i=first[cur]; i!=-1; i=next[i])        if (c[i]>0 && tag[to[i]]==TAG && !can[to[i]] && d[to[i]]==d[cur]-1)        {            k=dfs(to[i],min(num,c[i]));            if (k) num-=k,c[i]-=k,c[i^1]+=k;            if (num==0) break;        }    if (num) can[cur]=true;    return tmp-num;}bool _input(){    scanf("%d",&n);    s=addnode();    for (int i=1; i<=n; i++) t=addnode();    t=addnode();    for (int i=1; i<=n; i++) scanf("%d",&score[i]);    for (int i=1; i<=n; i++) scanf("%d",&test[i]);    for (int i=1; i<=n; i++)         for (int j=1; j<=n; j++)         {            scanf("%d",&a[i][j]);            if (!a[i][j] || i>=j) continue;            test[i]-=a[i][j],test[j]-=a[i][j];            if (i==1) score[1]+=a[i][j];                else                 {                    alltest+=a[i][j];                    int tmp=addnode();                    addedge(i,tmp,a[i][j]);                    addedge(j,tmp,a[i][j]);                    addedge(tmp,t,a[i][j]);                }        }    score[1]+=test[1];    for (int i=2; i<=n; i++)     {        if (score[i]>score[1]) return false;        addedge(s,i,score[1]-score[i]);    }    int ans=0;    while (bfs()) ans+=dfs(s,maxn);    return ans==alltest;}int main(){    if (_input()) puts("YES");        else puts("NO");    return 0;}


联系
我们