题目:http://acm.hdu.edu.cn/showproblem.php?pid=2452
题意:
题解:dp[i][0]表示从i点出发可以取得的最小值,dp[i][1]则表示最大值,即dp[[i][1]=max{ dp[j][0] } + value[i],dp[i][0]=min{ dp[j][1]
} + value[i],其中i到j有边。
代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 10005 #define N 1000005 #define inf 0xfffff int edge[N];//表示第i条边的终点 int next[N];//与第i条边同起点的下一条边的位置 int head[MAX];//以i为起点的第一条边的储存位置 int value[MAX];//第i个点的权值 int dp[MAX][2]; int cnt,n,m,f; bool in[MAX],out[MAX]; void insert(int a,int b)//a起点,b终点 { edge[++cnt]=b; next[cnt]=head[a]; head[a]=cnt; } int check(int st,int idx) { if(dp[st][idx]!=-1) return dp[st][idx]; dp[st][idx]=value[st]; int t=idx?0:inf; for(int i=head[st];i!=-1;i=next[i]) { if(idx) t=max(t,check(edge[i],0)); else t=min(t,check(edge[i],1)); } dp[st][idx]+=t; return dp[st][idx]; } int main() { int start; for(;~scanf("%d%d%d",&n,&m,&f);) { memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); memset(in,false,sizeof(in)); memset(out,false,sizeof(out)); for(int i=1;i<=n;++i) scanf("%d",value+i); for(;m--;) { int u,v; scanf("%d%d",&u,&v); insert(u,v); in[v]=out[u]=true; } memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;++i) { if(!out[i]) dp[i][0]=dp[i][1]=value[i]; else if(!in[i]) start=i; } if(check(start,1)>=f) puts("Victory"); else puts("Glory"); } return 0; }