# HDOJ 5424-Rikka with Graph II

HDOJ 5424-Rikka with Graph II
Rikka with Graph II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 379 Accepted Submission(s): 94
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains a number n(1≤n≤1000).
Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v.
Output
For each testcase, if there exist a Hamiltonian path print "YES" , otherwise print "NO".
Sample Input
4
1 1
1 2
2 3
2 4
3
1 2
2 3
3 1
Sample Output
NO
YES
Hint
For the second testcase, One of the path is 1->2->3
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

1）a在L的内部连接，这时A,B的度数都为1，其他点的度数为2或3；
2）a一端在A（或B），另一端在L的内部，这时L的另一个端点B（或A）的度数为1，其他点的度数为2或3；
3）a连接了A,B，此时所有点的度数都为2。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int kMaxN = 1005;
int degree[kMaxN];
vector<vector<int>> path;
int visit[kMaxN];
int n, done;
bool DFS(int s)
{
done++;
visit[s] = 1;
if (done == n)
return true;
int v;
for (int i = 0; i < path[s].size(); i++)
{
v = path[s][i];
if (!visit[v])
{
if (DFS(v))
return true;
}
}
done--;
visit[s] = 0;
return false;
}
bool CheckHamiltonian()
{
int min_degree = n + 1, bad_node_num = 0, id;
for (int i = 1; i <= n; i++)
{
if (degree[i] && degree[i] < min_degree)
{
min_degree = degree[i];
id = i;
}
if (degree[i] <= 1)
}
return false;
memset(visit, 0, sizeof(visit));
done = 0;
return DFS(id);
}
int main()
{
//freopen("input.txt", "r", stdin);
while (~scanf("%d", &n))
{
memset(degree, 0, sizeof(degree));
path.clear();
path.resize(n + 1);
int u, v;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &u, &v);
if (u == v)
continue;
degree[u]++;
degree[v]++;
path[u].push_back(v);
path[v].push_back(u);
}
if (CheckHamiltonian())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}


# HDOJ 5422-Rikka with Graph

HDOJ 5422-Rikka with Graph
Rikka with Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 144 Accepted Submission(s): 72
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and m edges. The length of each edge is 1. Now he wants to add exactly an edge which connects two different vertices and minimize the length of the shortest path between vertice 1 and vertice n. Now he wants to know the minimal length of the shortest path and the number of the ways of adding this edge.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains two numbers n,m(2≤n≤100,0≤m≤100).
Then m lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. There may be multiedges and self loops.
Output
For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice n and the number of the ways of adding this edge.
Sample Input
2 1
1 2
Sample Output
1 1
Hint
You can only add an edge between 1 and 2.
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main()
{
int n, m;
while (~scanf("%d %d", &n, &m))
{
bool connected = false;
int u, v;
while (m--)
{
scanf("%d %d", &u, &v);
if ((u == 1 && v == n) || (u == n&&v == 1))
connected = true;
}
if (connected)
printf("1 %d\n", n*(n - 1) / 2);
else
printf("1 1\n");
}
return 0;
}


# hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案
#1139 : 二分·二分答案

5 6 2 5
1 2 3
1 3 2
1 4 4
2 5 2
3 5 5
4 5 3

3

f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图，有可能TLE或MLE，使用邻接表更好。完整代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005;
vector<vector<int>> path;
vector<vector<int>> powers;
vector<bool> visit;
int n, m, k, t;
bool BFS(int power)
{
visit.clear();
visit.resize(n + 1, false);
queue<int> Q;
int u, v, len = 0;;
Q.push(1);
visit[1] = true;
Q.push(-1);
while (!Q.empty()&&len<k)
{
u = Q.front();
Q.pop();
if (u == -1)
{
if (Q.empty())
return false;
else
{
len++;
Q.push(-1);
continue;
}
}
for (int i = 0; i < path[u].size(); i++)
{
v = path[u][i];
if (!visit[v]&&powers[u][i] <= power)
{
if (v == t)
return true;
visit[v] = true;
Q.push(v);
}
}
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d %d %d %d", &n, &m, &k, &t);
path.resize(n + 1);
powers.resize(n + 1);
int u, v, w, low = kMaxW, high = 0;
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &u, &v, &w);
low = min(low, w);
high = max(high, w);
path[u].push_back(v);
path[v].push_back(u);
powers[u].push_back(w);
powers[v].push_back(w);
}
while (low+1 < high)
{
int mid = (low + high) / 2;
if (BFS(mid))
high = mid;
else
low = mid;
}
printf("%d\n", high);
return 0;
}


# hihoCoder week 60-1-String Matching Content Length

hihoCoder week 60-1-String Matching Content Length

We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings.
The first restriction here is that every common substring's length should not be less than 3. For example:
strA: abcdefghijklmn
strB: ababceghjklmn
The matching contents in strA and strB are substrings ("abc", "jklmn"). Note that though "e" and "gh" are common substrings of strA and strB, they are not matching content because their lengths are less than 3.
The second restriction is that the start indexes of all common substrings should be monotone increasing. For example:
strA: aaabbbbccc
strB: aaacccbbbb
The matching contents in strA and strB are substrings ("aaa", "bbbb"). Note that though "ccc" is common substring of strA and strB and has length not less than 3, the start indexes of ("aaa", "bbbb", "ccc") in strB are (0, 6, 3), which is not monotone increasing.

Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100.

The maximum length of matching contents (the sum of the lengths of the common substrings).

abcdefghijklmn
ababceghjklmn

8

The matching contents in strA and strB are substrings ("aaa", "bbbb"). Note that though "ccc" is common substring of strA and strB and has length not less than 3, the start indexes of ("aaa", "bbbb", "ccc") in strB are (0, 6, 3), which is not monotone increasing.

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int kMaxLen = 2105;
string a, b;
int dp[kMaxLen][kMaxLen][2];
int f[kMaxLen][kMaxLen];
void Init()
{
for (int i = 1; i < a.size(); i++)
{
for (int j = 1; j < b.size(); j++)
{
if (a[i] == b[j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = 0;
}
}
}
void Lcs()
{
for (int i = 1; i < a.size(); i++)
{
for (int j = 1; j < b.size(); j++)
{
dp[i][j][1] = 0;
if (f[i][j] >= 3)
{
dp[i][j][1] = max(dp[i][j][1], dp[i - 3][j - 3][0] + 3);
if (f[i][j]>3)
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][1] + 1);
}
dp[i][j][0] = max(dp[i - 1][j][0], max(dp[i][j - 1][0], dp[i][j][1]));
}
}
}
int main()
{
cin >> a >> b;
a = " " + a;
b = " " + b;
Init();
Lcs();
printf("%d\n", dp[a.size() - 1][b.size() - 1][0]);
return 0;
}


# hihoCoder 1138-Islands Travel

hihoCoder 1138-Islands Travel
#1138 : Islands Travel

There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) ..., (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island.

Line 1: an integer N.
Line 2~N+1: each line contains two integers Xi and Yi.
For 40% data, N<=1000，0<=Xi,Yi<=100000.
For 100% data, N<=100000，0<=Xi,Yi<=1000000000.

Output the minimum cost.

3
2 2
1 7
7 6

2

SPFA的介绍可以看我之前的题目。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int kMaxN = 100005, kINF = 0x3f;
int n;
typedef struct P
{
int x, y;
};
typedef struct Node
{
int value;
int id;
bool operator <(const Node & t)const
{
return value < t.value;
}
};
Node X[kMaxN], Y[kMaxN];
P points[kMaxN];
int dist[kMaxN];
int used[kMaxN];
vector<vector<int>> path(kMaxN);
inline int GetLength(int a, int b)
{
return min(abs(points[a].x - points[b].x), abs(points[a].y - points[b].y));
}
int Spfa()
{
used[1] = 1;
memset(dist, kINF, sizeof(dist));
dist[1] = 0;
queue<int> Q;
Q.push(1);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
used[u] = 0;
for (int i = 0; i < path[u].size(); i++)
{
int v = path[u][i];
if (dist[u] + GetLength(u, v) < dist[v])
{
dist[v] = dist[u] + GetLength(u, v);
if (used[v] == 0)
{
Q.push(v);
used[v] = 1;
}
}
}
}
return dist[n];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &points[i].x, &points[i].y);
X[i].value = points[i].x;
X[i].id = i;
Y[i].value = points[i].y;
Y[i].id = i;
}
sort(X + 1, X + n + 1);
sort(Y + 1, Y + n + 1);
for (int i = 2; i <= n; i++)
{
path[X[i].id].push_back(X[i - 1].id);
path[X[i - 1].id].push_back(X[i].id);
}
for (int i = 2; i <= n; i++)
{
path[Y[i].id].push_back(Y[i - 1].id);
path[Y[i - 1].id].push_back(Y[i].id);
}
printf("%d\n", Spfa());
return 0;
}


# HDOJ 3535-AreYouBusy

HDOJ 3535-AreYouBusy
AreYouBusy
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3450 Accepted Submission(s): 1342
Problem Description
Happy New Term!
As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad.
What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as "jobs". A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss's advice)?
Input
There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once.
Output
One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 .
Sample Input
3 3
2 1
2 5
3 8
2 0
1 0
2 1
3 2
4 3
2 1
1 1
3 4
2 1
2 5
3 8
2 0
1 1
2 8
3 2
4 4
2 1
1 1
1 1
1 0
2 1
5 3
2 0
1 0
2 1
2 0
2 2
1 1
2 0
3 2
2 1
2 1
1 5
2 8
3 2
3 8
4 9
5 10
Sample Output
5
13
-1
-1
Author
hphp
Source
2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU
Recommend
zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int kMaxN = 105, kINF = 0x7ffffff;
int dp[kMaxN][kMaxN];
int main()
{
//freopen("input.txt", "r", stdin);
int n, t;
while (~scanf("%d %d", &n, &t))
{
for (int i = 0; i < kMaxN; i++)
for (int j = 0; j < kMaxN; j++)
dp[i][j] = -kINF;
for (int i = 0; i < kMaxN; i++)
dp[0][i] = 0;
int m, s, c, g;
for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m--) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
else if (s == 1)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + g);
}
}
else if (s == 2)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
}
printf("%d\n", max(dp[n][t], -1));
}
return 0;
}


# hihoCoder 1137-Recruitment

hihoCoder 1137-Recruitment
#1137 : Recruitment

A company plans to recruit some new employees. There are N candidates (indexed from 1 to N) have taken the recruitment examination. After the examination, the well-estimated ability value as well as the expected salary per year of each candidate is collected by the Human Resource Department.
Now the company need to choose their new employees according to these data. To maximize the company's benefits, some principles should be followed:
1. There should be exactly X males and Y females.
2. The sum of salaries per year of the chosen candidates should not exceed the given budget B.
3. The sum of ability values of the chosen candidates should be maximum, without breaking the previous principles. Based on this, the sum of the salary per year should be minimum.
4. If there are multiple answers, choose the lexicographically smallest one. In other words, you should minimize the smallest index of the chosen candidates; If there are still multiple answers, then minimize the second smallest index; If still multiple answers, then minimize the third smallest one; ...
Your task is to help the company choose the new employees from those candidates.

The first line contains four integers N, X, Y, and B, separated by a single space. The meanings of all these variables are showed in the description above. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X + Y <= N, 1 <= B <= 1000.
Then follows N lines. The i-th line contains the data of the i-th candidate: a character G, and two integers V and S, separated by a single space. G indicates the gender (either "M" for male, or "F" for female), V is the well-estimated ability value and S is the expected salary per year of this candidate. 1 <= V <= 10000, 0 <= S <= 10.
We assure that there is always at least one possible answer.

On the first line, output the sum of ability values and the sum of salaries per year of the chosen candidates, separated by a single space.
On the second line, output the indexes of the chosen candidates in ascending order, separated by a single space.

4 1 1 10
F 2 3
M 7 6
M 3 2
F 9 9

9 9
1 2

DP的状态转移过程为：假设dpm[i][j]表示从【当前】所有男性中选取i个，工资总和为j时获得的最大能力总和。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int kMaxN = 105, kMaxB = 1005;
int dpf[kMaxN][kMaxB], dpm[kMaxN][kMaxB];//dpf[i][j]从所有女性应聘者中选取i个，工资总和为j时的最大能力和
unsigned long long idf[kMaxN][kMaxB][2];//记录女性选取情况
unsigned long long idm[kMaxN][kMaxB][2];//记录男性选取情况
int N, X, Y, B, V, S;
char G[2];
int ans_v = 0, ans_s = 0;//总能力，总工资
unsigned long long ans_id[2] = { 0 };//总选取情况
void DP()
{
dpf[0][0] = dpm[0][0] = 0;
int cnt_f = 0, cnt_m = 0, sum_s = 0;
for (int i = 1; i <= N; i++)
{
scanf("%s %d %d", G, &V, &S);
sum_s += S;
sum_s = min(sum_s, B);
if (G[0] == 'F')
{
cnt_f++;
cnt_f = min(cnt_f, Y);//最多选取Y位
for (int j = cnt_f; j >= 1; j--)
{
for (int k = sum_s; k >= S; k--)
{
if (dpf[j - 1][k - S] < 0)
continue;
if (dpf[j - 1][k - S] + V > dpf[j][k])
{
dpf[j][k] = dpf[j - 1][k - S] + V;
idf[j][k][0] = idf[j - 1][k - S][0];
idf[j][k][1] = idf[j - 1][k - S][1];
if (i <= 50)
idf[j][k][0] |= 1LL << (i - 1);//选中第i位
else
idf[j][k][1] |= 1LL << (i - 1 - 50);//选中第i位
}
}
}
}
else
{
cnt_m++;
cnt_m = min(cnt_m, X);
for (int j = cnt_m; j >= 1; j--)
{
for (int k = sum_s; k >= S; k--)
{
if (dpm[j - 1][k - S] < 0)
continue;
if (dpm[j - 1][k - S] + V > dpm[j][k])
{
dpm[j][k] = dpm[j - 1][k - S] + V;
idm[j][k][0] = idm[j - 1][k - S][0];
idm[j][k][1] = idm[j - 1][k - S][1];
if (i <= 50)
idm[j][k][0] |= 1LL << (i - 1);
else
idm[j][k][1] |= 1LL << (i - 1 - 50);
}
}
}
}
}
}
void Match()
{
for (int i = 0; i <= B; i++)
{
if (dpf[Y][i] == -1)
continue;
for (int j = 0; j + i <= B; j++)
{
if (dpm[X][j] == -1)
continue;
if (dpf[Y][i] + dpm[X][j] > ans_v)//能力更强
{
ans_v = dpf[Y][i] + dpm[X][j];
ans_s = i + j;
ans_id[0] = idf[Y][i][0] | idm[X][j][0];
ans_id[1] = idf[Y][i][1] | idm[X][j][1];
}
else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) < ans_s)//能力相同，但工资更少
{
ans_s = i + j;
ans_id[0] = idf[Y][i][0] | idm[X][j][0];
ans_id[1] = idf[Y][i][1] | idm[X][j][1];
}
else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) == ans_s)//能力和工资都相同
{
int id0 = idf[Y][i][0] | idm[X][j][0];
int id1 = idf[Y][i][1] | idm[X][j][1];
if (ans_id[0] > id0)//排序靠前
{
ans_id[0] = id0;
ans_id[1] = id1;
}
else if (ans_id[1] > id1)//排序靠前
{
ans_id[0] = id0;
ans_id[1] = id1;
}
}
}
}
}
void FormatOut()
{
printf("%d %d\n", ans_v, ans_s);
for (int i = 1; i <= 50; i++)
{
if (ans_id[0] & 1)
printf("%d ", i);
ans_id[0] >>= 1;
}
for (int i = 51; i <= 100; i++)
{
if (ans_id[1] & 1)
printf("%d ", i);
ans_id[1] >>= 1;
}
}
int main()
{
memset(dpf, -1, sizeof(dpf));
memset(dpm, -1, sizeof(dpm));
memset(idf, 0, sizeof(idf));
memset(idm, 0, sizeof(idm));
scanf("%d %d %d %d", &N, &X, &Y, &B);
DP();
Match();
FormatOut();
return 0;
}


# hihoCoder 1136-Professor Q's Software

hihoCoder 1136-Professor Q's Software
#1136 : Professor Q's Software

Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki signals: E1, E2, ..., EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started.

The first line contains an integer T, the number of test cases. T test cases follows.
For each test case, the first line contains contains two numbers N and M, indicating the number of modules and number of signals that Professor Q generates initially.
The second line contains M integers, indicating the signals that Professor Q generates initially.
Line 3~N + 2, each line describes an module, following the format S, K, E1, E2, ... , EK. S represents the signal that start up this module. K represents the total amount of signals that are generated during the lifecircle of this module. And E1 ... EK are these signals.
For 20% data, all N, M <= 10
For 40% data, all N, M <= 103
For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0 <= S, E <= 105.
Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended.

For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansi is the number of times that the i-th module is started. In case the answers may be too large, output the answers modulo 142857 (the remainder of division by 142857).

3
3 2
123 256
123 2 456 256
456 3 666 111 256
256 1 90
3 1
100
100 2 200 200
200 1 300
200 0
5 1
1
1 2 2 3
2 2 3 4
3 2 4 5
4 2 5 6
5 2 6 7

1 1 3
1 2 2
1 1 2 3 5

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int kMaxNMSE = 100005, kMaxK = 5, kMod = 142857;
int t, n, m, s, k;
int ans[kMaxNMSE];
int signals[kMaxNMSE];
vector<vector<int>> model_signals;
vector<vector<int>> signal_models;
queue<int> sgls;
void Init()
{
memset(ans, 0, sizeof(ans));
memset(signals, 0, sizeof(signals));
model_signals.clear();
model_signals.resize(kMaxNMSE);
signal_models.clear();
signal_models.resize(kMaxNMSE);
}
void BFS(int sgl)
{
sgls.push(sgl);
while (!sgls.empty())
{
int tmp = sgls.front();
sgls.pop();
if (signal_models[tmp].size())
{
for (int i = 0; i < signal_models[tmp].size(); i++)
{
int mdl = signal_models[tmp][i];
ans[mdl]++;
for (int j = 0; j < model_signals[mdl].size(); j++)
sgls.push(model_signals[mdl][j]);
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &t);
while (t--)
{
Init();
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &signals[i]);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &s, &k);
signal_models[s].push_back(i);
int tmp;
while (k--)
{
scanf("%d", &tmp);
model_signals[i].push_back(tmp);
}
}
for (int i = 1; i <= m; i++)
BFS(signals[i]);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i] % kMod);
printf("\n");
}
return 0;
}


# hihoCoder 1135-Magic Box

hihoCoder 1135-Magic Box
#1135 : Magic Box

The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever.
For example, let's assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish.

Line 1: x y z
Line 2: the sequence consisting of only three characters 'R', 'Y' and 'B'.
For 30% data, the length of the sequence is no more than 200.
For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20.

The maximum number of balls in the box ever.

Another Sample

 Sample Input Sample Output 0 0 0 RBYRRBY 4

1 2 3
RRYBRBRYBRY

7

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
int num_r=0,num_y=0,num_b=0,ans=0;
int xyz[3],diff[3];
string line;
void Work()
{
ans=max(ans,num_r+num_y+num_b);
diff[0]=abs(num_r-num_y);
diff[1]=abs(num_r-num_b);
diff[2]=abs(num_y-num_b);
sort(diff,diff+3);
if(diff[0]==xyz[0]&&diff[1]==xyz[1]&&diff[2]==xyz[2])
{
num_r=0;
num_y=0;
num_b=0;
}
}
int main()
{
cin>>xyz[0]>>xyz[1]>>xyz[2]>>line;
sort(xyz,xyz+3);
for(int i=0;i<line.size();i++)
{
switch(line[i])
{
case 'R':
num_r++;
break;
case 'Y':
num_y++;
break;
case 'B':
num_b++;
break;
}
Work();
}
printf("%d\n",ans);
return 0;
}


# HDOJ 5418-Victor and World

HDOJ 5418-Victor and World
Victor and World
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 643 Accepted Submission(s): 268
Problem Description
After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to n. They are connected by m undirected flights, detailedly the i-th flight connects the ui-th and the vi-th country, and it will cost Victor's airplane wi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country.
Victor now is at the country whose number is 1, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.
Input
The first line of the input contains an integer T, denoting the number of test cases.
In every test case, there are two integers n and m in the first line, denoting the number of the countries and the number of the flights.
Then there are m lines, each line contains three integers ui, vi and wi, describing a flight.
1≤T≤20.
1≤n≤16.
1≤m≤100000.
1≤wi≤100.
1≤ui,vi≤n.
Output
Your program should print T lines : the i-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.
Sample Input
1
3 2
1 2 2
1 3 3
Sample Output
10
Source
BestCoder Round #52 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5416 5415

$dp[s|(1<

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int kMaxN = 17, kINF = 0x3f3f3f3f;
int dis[kMaxN][kMaxN], dp[1 << kMaxN][kMaxN];
int n, m;
void Init()
{
memset(dis, 0x3f, sizeof(dis));
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++)
dis[i][i] = 0;
}
void Floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
}
int main()
{
freopen("input.txt", "r", stdin);
int t, u, v, w;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
Init();
while (m--)
{
scanf("%d %d %d", &u, &v, &w);
dis[u][v] = min(w, dis[u][v]);
dis[v][u] = dis[u][v];
}
Floyd();
dp[1][1] = 0;
for (int status = 1; status < (1 << n); status++)//枚举状态
{
for (int i = 1; i <= n; i++)//枚举最后访问的城市
{
//if (status&(1 << (i-1))==0)//(1)
if ((status&(1 << (i-1)))==0)//(2)i有没有访问过都可以
{
for (int j = 1; j <= n; j++)//枚举中间转折点
{
if (status&(1 << (j-1)))//(3)转折点j一定要访问过
dp[status | (1 << (i-1))][i] = min(dp[status | (1 << (i-1))][i], dp[status][j] + dis[i][j]);
}
}
}
}
int ans = kINF;
for (int i = 1; i <= n; i++)
ans = min(ans, dp[(1 << n) - 1][i] + dis[i][1]);
printf("%d\n", n == 1 ? 0 : ans);
}
return 0;
}