SPOJ 4556 Think I will Buy Me a Football Team

SPOJ_4556

    仔细分析一下的话可以得到最简的状态是对于任意一个点要么只有入度，要么只有出度，否则是可以通过构造得到更优的解的。

    这样问题就变成了只要欠钱的人掏钱直接给赊账的人就可以了，也就说没有中转人。于是只要读完数据统计一下欠钱的人一共欠了多少就可以了。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
int h[MAXD], N;
void solve()
{
    int i, j, k, tot = 0, ans = 0;
    memset(h, 0, sizeof(h[0]) * N);
    for(i = 0; i < N; i ++)
        for(j = 0; j < N; j ++)
        {
            scanf("%d", &k), tot += k;
            h[i] += k, h[j] -= k;
        }
    for(i = 0; i < N; i ++) if(h[i] > 0) ans += h[i];
    printf("%d %d\n", tot, ans);
}
int main()
{
    int t = 0;
    for(;;)
    {
        scanf("%d", &N);
        if(N == 0)
            break;
        printf("%d. ", ++ t);
        solve();
    }
    return 0;    
}