E. Coin Troubles time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
In the Isle of Guernsey there are n different types of coins. For each i (1 ≤ i ≤ n), coin of type i is worth ai cents. It is possible that ai = ajfor some i and j (i ≠ j).
Bessie has some set of these coins totaling t cents. She tells Jessie q pairs of integers. For each i (1 ≤ i ≤ q), the pair bi, ci tells Jessie that Bessie has a strictly greater number of coins of type bi than coins of type ci. It is known that all bi are distinct and all ci are distinct.
Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some i (1 ≤ i ≤ n), such that the number of coins Bessie has of type i is different in the two combinations. Since the answer can be very large, output it modulo 1000000007 (109 + 7).
If there are no possible combinations of coins totaling t cents that satisfy Bessie's conditions, output 0.
Input
The first line contains three space-separated integers, n, q and t (1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 105). The second line contains n space separated integers, a1, a2, ..., an (1 ≤ ai ≤ 105). The next q lines each contain two distinct space-separated integers, bi and ci(1 ≤ bi, ci ≤ n; bi ≠ ci).
It's guaranteed that all bi are distinct and all ci are distinct.
Output
A single integer, the number of valid coin combinations that Bessie could have, modulo 1000000007 (109 + 7).
Examples input
4 2 17
3 1 2 5
4 2
3 4
output
3
input
3 2 6
3 1 1
1 2
2 3
output
input
3 2 10
1 2 3
1 2
2 1
output
Note
For the first sample, the following 3 combinations give a total of 17 cents and satisfy the given conditions: {0 of type 1, 1 of type 2, 3 of type 3, 2 of type 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.
No other combinations exist. Note that even though 4 occurs in both bi and ci, the problem conditions are still satisfied because all bi are distinct and all ci are distinct.
題目大意：
有n種硬币，現在我們需要湊出t價值的硬币，我們每種硬币都可以任取數量，不過要滿足q個限制。
對于每個限制，（a，b）表示需要a種類的硬币使用的個數多餘b種類的硬币。
思路：
①對于依賴（a，b），如果我們拿了一個b硬币，那麼肯定同時也要拿至少一個a硬币，那麼我們可以預處理一下，令一開始的時候，我們是滿足所有限制條件的。
那麼過程其實就相當于建個反圖，然後将t-=a【i】*d，d表示從度為0的點拓撲到目前點鍊的長度。這樣的話我們就能夠使得初始的時候，我們是滿足所有限制條件的。
②那麼接下來，我們考慮拿一個b硬币的時候，同時也要再拿一個a硬币才能繼續保證滿足限制條件。是以我們再拓撲排序一下過程使得a【v】+=a【u】，然後建構出新的物品集合，然後再跑完全背包即可。
具體細節參考代碼；
Ac代碼：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define mod 1000000007
#define ll __int64
ll wupin[350];
vector<ll>mp[350];
ll a[350];
ll b[350];
ll dp[150000];
ll degree[150000];
ll vis[150000];
ll n,q,t;
void Top()
{
queue<ll>s;
memset(dp,0,sizeof(dp));
for(ll i=1;i<=n;i++)
{
if(degree[i]==0)
{
s.push(i);
}
}
ll cnt=0;
int cont=0;
while(!s.empty())
{
ll u=s.front();s.pop();
cont++;
if(vis[u]>0)t-=a[u]-b[u];
if(a[u]<=t)wupin[cnt++]=a[u];
for(ll i=0;i<mp[u].size();i++)
{
ll v=mp[u][i];
a[v]+=a[u];
degree[v]--;
if(degree[v]==0)s.push(v);
}
}
dp[0]=1;
for(ll i=0;i<cnt;i++)
{
for(ll j=wupin[i];j<=t;j++)
{
dp[j]+=dp[j-wupin[i]];
dp[j]%=mod;
}
}
if(t>=0&&cont==n)
printf("%I64d\n",dp[t]);
else printf("0\n");
}
int main()
{
while(~scanf("%I64d%I64d%I64d",&n,&q,&t))
{
memset(vis,0,sizeof(vis));
memset(degree,0,sizeof(degree));
for(ll i=1;i<=n;i++)mp[i].clear();
for(ll i=1;i<=n;i++)scanf("%I64d",&a[i]),b[i]=a[i];
for(ll i=0;i<q;i++)
{
ll x,y;scanf("%I64d%I64d",&x,&y);
vis[x]++,vis[y]++;
mp[x].push_back(y);
degree[y]++;
}
Top();
}
}