HDU5503 EarthCup

Link
我们有一个网络流做法，左边({nchoose 2})个点，右边(n)个点，其中右边的点到汇点的流量为(a_i)，然后判断该图能否满流。
如果我们把每个右部点拆成(a_i)个，那么就是问左右各有({nchoose 2})个点的二分图是否有完美匹配。
考虑Hall定理，不难发现有完美匹配的充要条件是，将({a})升序排序后，(forall iin[1,n],sumlimits_{j=1}^ia_ige{ichoose 2})。

#include<cstdio>
#include<algorithm>
int a[50007];
int read(){int x;scanf("%d",&x);return x;}
void solve()
{
    int n=read(),sum=0,flg=1;
    for(int i=1;i<=n;++i) a[i]=read();
    std::sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) if((sum+=a[i])<i*(i-1ll)/2) flg=0;
    puts(flg&&sum==n*(n-1ll)/2? "It seems to have no problem.":"The data have been tampered with!");
}
int main(){for(int T=read();T;--T) solve();}