中石油acm4985: Going Dutch 还钱问题（状压dp）

4985: Going Dutch

时间限制: 1 Sec  内存限制: 128 MB
提交: 102  解决: 11
[提交][状态][讨论版][命题人:admin]

题目描述

You and your friends have just returned from a beautiful vacation in the mountains of the Netherlands. When on vacation, it’s annoying to split the bill on every expense every time, so you just kept all the receipts from the vacation, and wrote down who paid how much for who. Now, it is time to settle the bill.
You could each take all the receipts showing that someone paid something for you, and then pay that person back. But then you would need a lot of transactions, and you want to keep up the lazy spirit from your trip. In the end, it does not matter who transfers money to whom; as long as in the end, everyone’s balance is 0.
Can you figure out the least number of transactions needed to settle the score? Assume everyone has enough spare cash to transfer an arbitrary amount of money to another person.

输入

Input consists of
• A line containing two integers M, the number of people in the group, with 1 ≤ M ≤ 20,and N, the number of receipts from the trip, with 0 ≤ N ≤ 1000.
• N lines, each with three integers a, b, p, where 0 ≤ a, b < M, and 1 ≤ p ≤ 1000,signifying a receipt showing that person a paid p euros for person b.

输出

Output a single line containing a single integer, the least number of transactions necessary to settle all bills.

样例输入

4 2
0 1 1
2 3 1

样例输出

2

【题意】

有n个人之间存在借钱问题，问最少发生几次还钱行为，使这n个人之间还清。

【分析】

n个人至多可以有n-1次还钱行为即可还清（树图），若能把n个人分为两个集合，每个集合内能还清，则最多需要n-2次还钱行为。

若能把n个人分为k个能各自还清的集合，则需要n-k次还钱行为。故此题最大化k即可。

 

状态压缩。用一个数字代表一个状态，其二进制位上为1，代表此人选中，0代表不选。

每个数字代表一个集合。

【代码】

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[30],dp[1<<22],b[1<<22];
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        a[x]-=z;
        a[y]+=z;
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)if(i&(1<<j))
        {
            b[i]+=a[j];
        }
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)if((i&(1<<j))==0)
        {
            dp[i|(1<<j)]=max(dp[i|(1<<j)],dp[i]+(b[i|(1<<j)]==0));
        }
    }
    cout<<n-dp[(1<<n)-1]<<endl;
}

View Code