【郑轻邀请赛 E】Can Win

【题目链接】:https://acm.zzuli.edu.cn/zzuliacm/problem.php?id=2131

【题意】

【题解】



尽量让自己喜欢的队赢;

A内组内的比赛都让自己喜欢的队赢;

其他的队

对于a[i][j],先让i和j中分数小的队的分数赶上分数高的队的分数;

然后剩下的平均分;

对于剩下的人和B组的比赛,都让他们输就好;

而自己支持的队和B组的比赛都让他们赢;

这样自己支持的队的分数达到了最大化;

其他人的队的分数尽可能地小了;

这个时候再判断自己喜欢的队是不是最高分;



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define rep1(i,x,y) for (int i = x;i <= y;i++)

#define LL long long

const int N = 4e2+100;

int n,k;

LL mark[N],cnt[N],a[N][N];

int main()

{

    //freopen("D:\\rush.txt","r",stdin);

    ios::sync_with_stdio(0);

    int T;

    cin >> T;

    while (T--)

    {

       cin >> n >> k;

       rep1(i,1,n)

            cin >> mark[i];

       rep1(i,1,n)

            cin >> cnt[i];

       rep1(i,1,n)

            rep1(j,1,n)

            {

                cin >>a[i][j];

            }

       rep1(i,1,n)

       {

            mark[k]+=a[k][i];

            cnt[k]-=a[k][i];

            a[k][i] = a[i][k] = 0;

       }

       mark[k]+=cnt[k];cnt[k] = 0;

       rep1(i,1,n-1)

           rep1(j,i+1,n)

            if (a[i][j])

                {

                    if (mark[i]<mark[j])

                    {

                        mark[i]+=min(mark[j]-mark[i],a[i][j]);

                        a[i][j]-=min(mark[j]-mark[i],a[i][j]);

                    }

                    else

                    {

                        mark[j]+=min(mark[i]-mark[j],a[i][j]);

                        a[i][j]-=min(mark[i]-mark[j],a[i][j]);

                    }

                    mark[i]+=a[i][j]/2;

                    mark[j]+=a[i][j]-a[i][j]/2;

                }

        bool fi = false;

        rep1(i,1,n)

            if (mark[i]>mark[k])

                fi = true;

        if (fi)

            puts("No");

        else

            puts("Yes");

    }

    return 0;

}