[UVA][dp] 11655 - Waterland
|
J |
Water Land Input: Standard Input Output: Standard Output |
The year 3110. Most of the lands have disappeared under water, leaving many small islands. Waterland is a peaceful country consisting of many such islands. All islands in Waterland are connected by tunnels. Each tunnel connects exactly two islands. Tunnels are very expensive to build, so WRTA (Waterland Road and Tunnel Authorities) tries to keep the number of tunnels as low as possible. (You may be wondering why not just use air transport! Air transport can no longer be used due to terrible weather condition.)
President of Waterland wants to spend his upcoming vacation in Yablonoi Island, after the long and tedious hours of work at office (Kurai Island). The Elite Security Force (ESF) of Waterland, who is responsible for president’s security, always takes precautions before his journey. They have selected some of the safe tunnels from Kurai Island to Yablonoi island. Safe tunnels are chosen in such a way that if anyone starts to travel from Kuriai island to Yablonoi Island, it is not possible to visit any island twice with any possible route.
ESF sends a group of teams in all routes from Kurai Island to Yablonoi Island. Each group of teams drops one team at each island (except Kuroi – the president’s office) on their route and moves on. At the end, for each route, only one team from each group will reach in Yablonoi Island. Therefore, one island may contain multiple teams from different groups. Now the Chief of ESF asks you to calculate the total number of teams required for the whole process and the number of teams reached at destination (Yablonoi Island).
Input
First line of the input represents the number of test cases N (N≤40). Each test case starts with a line containing 2 numbers L and T, where L represents the number of island (2 ≤ L ≤ 5000) in that country and T (0≤T≤5*L) represents the number of safe tunnels. After that, there will be T lines with two numbers: x and y (1≤ x,y ≤ L) representing the tunnel between island x and island y. All of these tunnels are one way (from x to y) on that day (for the sake of president’s safety). There will be at most one tunnel between any two islands. Consider the “island 1” as Kurai island and “island L” as Yablonoi island.
Output
For each test case, print the case number first followed by two numbers, S and D where S represents the number of teams that is required by ESF for the whole process and D represents the number of teams that reached in the meeting place after the whole operation. Print both numbers (S and D) in modulo 1,00,000.
Sample Input Output for Sample Input
|
3 2 1 1 2 4 4 1 2 1 3 2 4 3 4 4 3 1 2 2 3 3 4 |
Case 1: 1 1 Case 2: 4 2 Case 3: 3 1 |
Problem setter: Syed Monowar Hossain, Special Thanks: Md. Arifuzzaman Arif
保證所有點都可以從起點到達，並且可以抵達終點，同時圖形也是個 DAG，計算所有可能路徑個數，以及所有可能路徑中的邊總數。
題目事實上是描述有軍團，軍團內又有好幾個小組，軍團嘗試所有路徑移動到終點，並且沿途拋下一個小組留下。問總共需要幾個小組，以及最後有多少個小組抵達(終點只能有一個小組抵達)。
題目解法：
計算路徑本身不難，通常我們會使用 dp[node1] += dp[node2], 其中 node2->node1。
那麼計算有多少邊也是相同的，edge[node1] += dp[node2], 其中 node2->node1
也就是說 node2->node1 會走過 dp[node2] 次。
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
vector<int> g[5005], vg[5005];
void sol(int n) {
int i, j;
queue<int> Q;
int indeg[5005] = {}, dp[5005] = {}, dp2[5005] = {};
for(i = 1; i <= n; i++) {
for(j = 0; j < g[i].size(); j++) {
indeg[g[i][j]]++;
}
}
int S, D;
dp[1] = 1;
for(i = 1; i <= n; i++)
if(indeg[i] == 0)
Q.push(i);
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
for(i = 0; i < g[tn].size(); i++) {
dp[g[tn][i]] += dp[tn];
dp2[g[tn][i]] += dp2[tn]+dp[tn];
dp[g[tn][i]] %= 100000;
dp2[g[tn][i]] %= 100000;
if(--indeg[g[tn][i]] == 0)
Q.push(g[tn][i]);
}
}
D = dp[n];
S = dp2[n];
printf("%d %d\n", S, D);
}
int main() {
int testcase, cases = 0;
int n, m, x, y, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
g[i].clear(), vg[i].clear();
while(m--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
vg[y].push_back(x);
}
printf("Case %d: ", ++cases);
sol(n);
}
return 0;
}
/*
1
7 9
1 2
1 3
1 4
2 4
3 4
4 5
4 6
5 7
6 7
*/