别用pascal啦小哥

#include <iostream>
#include <vector>
#include <algorithm>
#define num long long int
#define For(i, j, k) for(num i = j; i <= k; i++)
#define For_it(i, j, k) for(vector<num>::iterator i = j; i != k; i++)

using namespace std;
num n;
vector<num> t[1501];
num c[1501];

num ans[1501];

num f(num x){
if (ans[x] != 0){
return ans[x];
}

if (t[x].empty()){
return ans[x] = c[x];
}

num re = c[x];

For_it(i, t[x].begin(), t[x].end()){
For_it(j, (t[*i]).begin(), (t[*i]).end()){
re += f(*j);
}
}

num w;
For_it(i, t[x].begin(), t[x].end()){
w = 0;
w += c[(*i)];

For_it(j, t[(*i)].begin(), t[(*i)].end()){
if (!t[(*j)].empty()){
For_it(k, t[(*j)].begin(), t[(*j)].end()){
w += f(*k);
}
}
}

For_it(j, t[x].begin(), t[x].end()){
if (j != i){
w += f(*j);
}
}

re = min(re, w);
}
return ans[x] = re;
}

bool u[1501];

int main(){

cin >> n;

if (n == 0){
cout << 0 << endl;
}
if (n != 0) {
For(i, 1, n) {
num x0, x1, x2;
cin >> x0 >> x1 >> x2;

c[x0] = x1;
For(j, 1, x2) {
cin >> x1;
u[x1] = true;
t[x0].push_back(x1);
}
}

For(i, 1, n) {
if (!u[i]) {
cout << f(i) << endl;
}
}

}
return 0;
}

第六组RA+1，所以到底是为什么？？

记录信息
评测状态 Wrong Answer
题目 P1144 小胖守皇宫
递交时间 2015-10-07 11:47:05
代码语言 C++
评测机 VijosEx
消耗时间 45 ms
消耗内存 636 KiB
评测时间 2015-10-07 11:47:06
评测结果
编译成功

foo.cpp: In function 'void search(int, int)':
foo.cpp:14:6: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
int flag=1;
^
测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 14
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 14
测试数据 #2: Accepted, time = 0 ms, mem = 588 KiB, score = 14
测试数据 #3: Accepted, time = 15 ms, mem = 636 KiB, score = 14
测试数据 #4: Accepted, time = 15 ms, mem = 580 KiB, score = 14
测试数据 #5: WrongAnswer, time = 15 ms, mem = 576 KiB, score = 0
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 14
WrongAnswer, time = 45 ms, mem = 636 KiB, score = 84
代码
#include <iostream>
#include <stdio.h>
#define inf 1000000000;
using namespace std;
int fir[1510];
int nxt[3020];
int link[3020];
int dp[1510][3];
int cost[1510];
int cnt;
void Link(int a,int b){nxt[++cnt]=fir[a];link[cnt]=b;fir[a]=cnt;}
void search(int now,int pre)
{
int flag=1;
dp[now][1]=cost[now];
int mi=inf;
for(int i=fir[now];i;i=nxt[i])
{
if(link[i]!=pre){
flag=0;
search(link[i],now);
dp[now][0]+=min(dp[link[i]][1],dp[link[i]][0]);
dp[now][1]+=min(dp[link[i]][2],dp[link[i]][0]);
dp[now][2]+=min(dp[link[i]][0],dp[link[i]][1]);

if(dp[link[i]][1]<=dp[link[i]][0])mi=0;
if(mi&&dp[link[i]][1]-dp[link[i]][0]<mi){
mi=dp[link[i]][1]-dp[link[i]][0];
}
}
}
dp[now][0]+=mi;
}
int main()
{
int n;
scanf("%d",&n);
int m=n;
while(m--)
{
int a,b,k;
scanf("%d",&a);
scanf("%d",&cost[a]);
scanf("%d",&k);
while(k--){
scanf("%d",&b);
Link(a,b);
Link(b,a);
}
}

search(1,1);

printf("%d",min(dp[1][0],dp[1][1]));
}

记录信息
评测状态 Accepted
题目 P1144 小胖守皇宫
递交时间 2015-10-07 12:12:02
代码语言 C++
评测机 VijosEx
消耗时间 57 ms
消耗内存 636 KiB
评测时间 2015-10-07 12:12:03
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 14
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 14
测试数据 #2: Accepted, time = 0 ms, mem = 580 KiB, score = 14
测试数据 #3: Accepted, time = 15 ms, mem = 636 KiB, score = 14
测试数据 #4: Accepted, time = 12 ms, mem = 580 KiB, score = 14
测试数据 #5: Accepted, time = 15 ms, mem = 584 KiB, score = 14
测试数据 #6: Accepted, time = 15 ms, mem = 576 KiB, score = 14
Accepted, time = 57 ms, mem = 636 KiB, score = 98
代码
#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=2100000000;
int fir[1510];
int nxt[3020];
int link[3020];
int dp[1510][3];
/*dp[now][0]表示now点不安置守卫的最低花费，而是通过其子节点的守卫守卫,dp[now][1]表示now点安置守卫的最低花费,dp[now][2]表示now点不安置守卫，而是通过其父节点的守卫守卫的最低花费*/
int cost[1510]; //每个点的花费
int cnt;
void Link(int a,int b){nxt[++cnt]=fir[a];link[cnt]=b;fir[a]=cnt;}
void search(int now,int pre)
{
dp[now][1]=cost[now];
dp[now][2]=0;
int flag=inf;
for(int i=fir[now];i;i=nxt[i])
{
if(link[i]!=pre){
search(link[i],now);//先向下走，再从下往上DP

dp[now][0]+=min(dp[link[i]][1],dp[link[i]][0]);
dp[now][1]+=min(dp[link[i]][1],min(dp[link[i]][2],dp[link[i]][0]));
dp[now][2]+=min(dp[link[i]][0],dp[link[i]][1]);

//DP

if(dp[link[i]][1]<=dp[link[i]][0])flag=0;
if(flag&&dp[link[i]][1]-dp[link[i]][0]<flag){
flag=dp[link[i]][1]-dp[link[i]][0];
}
//特判，由于dp[now][0]只需要其某一个‘now的子节点’有守卫即可，需特殊处理
}
}

dp[now][0]+=flag; //当now没有子节点时，dp[now][0]=inf;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b,k;
scanf("%d",&a);
scanf("%d",&cost[a]);
scanf("%d",&k);
while(k--){
scanf("%d",&b);
Link(a,b);
Link(b,a);
}
}
search(1,0);
printf("%d",min(dp[1][0],dp[1][1]));
}