【思维】图论+贪心——NCPC 2019 Incremental Induction

理解成图上对应关系就好想得多

如果s[i][j]=‘0’,那么从i向j连一条边，最后形成的图必定是完全图

当右边有t人时，右边输给左边的总场数为sum(out(i))-t*(t-1)/2,

即右边到左边的边总数=右边的点出度和-右边点自己和自己连的边

所以要让k最小，只要给出度排个序即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
struct node
{
 int val, id;
}peo[maxn];
bool cmp(node a, node b)
{
 return a.val < b.val;
}
bool arr[maxn][maxn], vis[maxn];
int main()
{
 long long n;
 cin >> n;
 for(int i = 1; i <= n; i++) peo[i].id = i;
 for(int i = 2; i <= n; i++)
 for(int j = 1; j < i; j++)
 {
 scanf("%1d", &arr[i][j]);
 arr[j][i] = (arr[i][j] ^ 1);
 if(arr[i][j] == 1) peo[i].val++;
 else peo[j].val++;
 }
 sort(peo + 1, peo + 1 + n, cmp);
 long long ans = 0, now = 0;
 for(int i = 1; i <= n; i++)
 {
 vis[peo[i].id] = 1;
 for(int j = 1; j <= n; j++)
 {
     if(i == j) continue;
 if(arr[peo[i].id][peo[j].id] && !vis[peo[j].id])
 now++;
 else if(arr[peo[j].id][peo[i].id] && vis[peo[j].id])
 now--;
 }
 ans = max(ans, now);
 }
 cout << ans << endl; }