题解：CF283C Coin Troubles

题目链接：https://codeforces.com/problemset/problem/283/C

题意：

有 n 种硬币，每种硬币都有一个价格 ai，现在有 q 个限制，每个限制会告诉你 (b,c)，并要求 b 种硬币的数量严格大于 c 种硬币的数量。现在问你一共有多少种买硬币的方法，使得最后买硬币一共要 t 元。答案最后要求对 10^9+7 取模。

思路：

对于每一个限制，我们首先想到，如果对于一个数，它限制的数如果限制了它本身，那么肯定一种方法都没有。刨去这种特殊情况，如果将每一种限制画出来连在一起（未限制和被限制的点单独出现），直观的看就是多个有向无环图，容易想到拓扑序，也就可以看成多个树和多个点。考虑每条链的最小贡献，对于每一个被限制的点，我们每次可以将它的所有父亲节点的值从 t 中减去，这样子就可以满足被限制的点的数量严格小于限制它的点的数量。

对于每一条链，我们可以把它作为一个整体考虑贡献，这样子我们就可以把这道题转化为完全背包了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long // 不开long long见祖宗

const int N = 1e5 + 10, M = 310, mod = 1e9 + 7;
int k[M * 4], f[M][N], s[M], p[N], dp[N], fa[M];
int n, q, t;
vector <int> nxt[M];
int find(int x)
{
    if(p[x] == 0) return s[x];
    int fa = find(p[x]);
    return fa + s[x];
}
int find2(int x) // 找父亲
{
    return fa[x] == x ? x : fa[x] = find2(fa[x]);
}

signed main()
{
    int op = 0;
    cin >> n >> q >> t;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= n; i++) fa[i] = i; // 预处理
    for(int i = 1; i <= q; i++)
    {
        int a, b;
        cin >> a >> b;
        if(find2(a) == find2(b)) // 找到环了
        {
            cout << '0';
            return 0;
        }
        fa[find2(a)] = find2(b);
        p[b] = a;
    }
    for(int i = 1; i <= n; i++)
    {
        if(p[i]) 
        {
            k[++op] = find(i);
            t -= (k[op] - s[i]);
        }
        else k[++op] = s[i];
    }
    if(t < 0) // 需要的硬币比拥有的硬币多，直接cout 0
    {
        cout << '0';
        return 0;
    }
    dp[0] = 1;
    for(int i = 1; i <= op; i++) // 完全背包
    {
        for(int l = 0; l + k[i] <= t; l++)
        {
            dp[l + k[i]] = (dp[l + k[i]] + dp[l]) % mod;
        }
    }
    cout << dp[t] % mod;
}

（本蒟蒻的第一篇题解，如有错误多多指正）