Coin Troubles题解（dp,拓扑序）

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

题意：

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

思路：

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

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

代码如下：

#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;
}

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