2012-C12-team3
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
这场比赛做的很不好，主要责任在我
开场第一题，很简单，我上去写了结果WA，因为题意没想清楚，多算了一种情况
然后B题又是我写过无数遍的最短路dp，结果写wa了，检查了接近20分钟才发现错误，原因是初始状态dp[ss.x][ss.c]=0忘了写，以后一定要记住别再犯这种2b错误
G题是整场比赛最大的悲剧，这题是我写的，一开始逻辑没想清楚，不够全面，wa了，后来不断的改还是错，还剩2个小时的时候让lh学长帮我一起想
lh学长多次提出可以尝试记忆化搜索，但都被我否决了，原因是我没想到字符串可以直接弄成数字去hash，固执的认为这样会超时，事实上其他队伍基本都是这样1Y的。。
这是我犯的第一个错误
最后一个小时，我重新梳理的题目给出的递归程序，才发现只要出现a<b的情况，就永远都是a<b了，所以我之前的逻辑判断方法基本是正确的，但是不知道哪里错了
此时我又犯了第二个错误，就是算法确定正确性后，没有回去仔细检查代码，大概花了30分钟在空想
最后20分钟，我突然想起我的代码有一种情况没有判断，这种情况导致了我第一次提交的时候是RTE，我当时选择的做法是直接跳过这种情况来避免RTE，后来仔细想才发现这样有bug
改了之后10Y。。
这场比赛我过于独断，有点自大了。。然后在比赛不顺的时候，有点着急、心乱，说实话我现在还不知道怎么应对这种情况比较好。。
接下来的比赛要让striver和lh学长多提醒我一下，先尽量避免把，如果再次遇到逆境，一定要和队友沟通，不要一个人蛮干
--大肥羊
}}}
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
int s, t, w, num;
friend bool operator < (edge n1, edge n2)
{
return n1.w < n2.w;
};
};
edge ed[100000];
bool f[100000], f1[100000];
int e[100000], next[100000], lin[100000], top;
void connect(int j, int k)
{
top ++;
e[top] = k; next[top] = lin[j]; lin[j] = top;
top ++;
e[top] = j; next[top] = lin[k]; lin[k] = top;
}
bool dfs(int i, int j)
{
// cout << i << endl;
if (f[i]) return true;
int p = lin[i];
while (p) {
if (f1[p] && e[p] != j)
if (dfs(e[p], i)) return true;
p = next[p];
}
return false;
}
int main()
{
int tt = 0, n, m, p, ans, i, j;
while (cin >> n >> m >> p){
if (n == 0 && m == 0 && p == 0) break;
tt ++; top = 0;
for (i = 1; i <= n; i ++) lin[i] = 0,f[i] = false;
for (i = 1; i < n; i ++) {
cin >> ed[i].s >> ed[i].t >> ed[i].w;
ed[i].num = i;
connect(ed[i].s, ed[i].t);
}
sort(ed + 1, ed + n);
for (i = 1; i <= n; i ++) f[i] = false;
for (i = 1; i <= m; i ++) {
cin >> j; f[j] = true;
}
for (i = 1; i <= top; i ++) f1[i] = true;
ans = 0;
for (i = 1; i < n; i ++) {
if (!p) break;
f1[ed[i].num * 2] = false; f1[ed[i].num * 2 - 1] = false;
// cout << ans << endl;
if (dfs(ed[i].s, 0) && dfs(ed[i].t, 0)) {
ans += ed[i].w; p --;
}
else { f1[ed[i].num * 2] = true; f1[ed[i].num * 2 - 1] = true; }
// cout << "hdsf " << endl;
}
printf("Case %d: %d\n", tt, ans);
}
return 0;
}这场比赛做的很不好，主要责任在我
开场第一题，很简单，我上去写了结果WA，因为题意没想清楚，多算了一种情况
然后B题又是我写过无数遍的最短路dp，结果写wa了，检查了接近20分钟才发现错误，原因是初始状态dp[ss.x][ss.c]=0忘了写，以后一定要记住别再犯这种2b错误
G题是整场比赛最大的悲剧，这题是我写的，一开始逻辑没想清楚，不够全面，wa了，后来不断的改还是错，还剩2个小时的时候让lh学长帮我一起想
lh学长多次提出可以尝试记忆化搜索，但都被我否决了，原因是我没想到字符串可以直接弄成数字去hash，固执的认为这样会超时，事实上其他队伍基本都是这样1Y的。。
这是我犯的第一个错误
最后一个小时，我重新梳理的题目给出的递归程序，才发现只要出现a<b的情况，就永远都是a<b了，所以我之前的逻辑判断方法基本是正确的，但是不知道哪里错了
此时我又犯了第二个错误，就是算法确定正确性后，没有回去仔细检查代码，大概花了30分钟在空想
最后20分钟，我突然想起我的代码有一种情况没有判断，这种情况导致了我第一次提交的时候是RTE，我当时选择的做法是直接跳过这种情况来避免RTE，后来仔细想才发现这样有bug
改了之后10Y。。
这场比赛我过于独断，有点自大了。。然后在比赛不顺的时候，有点着急、心乱，说实话我现在还不知道怎么应对这种情况比较好。。
接下来的比赛要让striver和lh学长多提醒我一下，先尽量避免把，如果再次遇到逆境，一定要和队友沟通，不要一个人蛮干
--大肥羊
#include
#include
#include
using namespace std;
struct edge {
int s, t, w, num;
friend bool operator < (edge n1, edge n2)
{
return n1.w < n2.w;
};
};
edge ed[100000];
bool f[100000], f1[100000];
int e[100000], next[100000], lin[100000], top;
void connect(int j, int k)
{
top ++;
e[top] = k; next[top] = lin[j]; lin[j] = top;
top ++;
e[top] = j; next[top] = lin[k]; lin[k] = top;
}
bool dfs(int i, int j)
{
// cout << i << endl;
if (f[i]) return true;
int p = lin[i];
while (p) {
if (f1[p] && e[p] != j)
if (dfs(e[p], i)) return true;
p = next[p];
}
return false;
}
int main()
{
int tt = 0, n, m, p, ans, i, j;
while (cin >> n >> m >> p){
if (n == 0 && m == 0 && p == 0) break;
tt ++; top = 0;
for (i = 1; i <= n; i ++) lin[i] = 0,f[i] = false;
for (i = 1; i < n; i ++) {
cin >> ed[i].s >> ed[i].t >> ed[i].w;
ed[i].num = i;
connect(ed[i].s, ed[i].t);
}
sort(ed + 1, ed + n);
for (i = 1; i <= n; i ++) f[i] = false;
for (i = 1; i <= m; i ++) {
cin >> j; f[j] = true;
}
for (i = 1; i <= top; i ++) f1[i] = true;
ans = 0;
for (i = 1; i < n; i ++) {
if (!p) break;
f1[ed[i].num * 2] = false; f1[ed[i].num * 2 - 1] = false;
// cout << ans << endl;
if (dfs(ed[i].s, 0) && dfs(ed[i].t, 0)) {
ans += ed[i].w; p --;
}
else { f1[ed[i].num * 2] = true; f1[ed[i].num * 2 - 1] = true; }
// cout << "hdsf " << endl;
}
printf("Case %d: %d\n", tt, ans);
}
return 0;
}