|
题目描述 Description |
|
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。 |
|
输入描述 Input Description |
|
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。 |
|
输出描述 Output Description |
|
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。 |
|
样例输入 Sample Input |
|
3 10 2 20 3 30 1 |
|
样例输出 Sample Output |
|
30 |
|
数据范围及提示 Data Size & Hint |
|
N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。 |
之前的一些废话：是时候准备会考了。。
题解：
有点恶心的题。
解法1：首先考虑n个点n条边的连通图，如果是n个点n-1条边那就是一棵树，再加一条边就是一个环，环上再支出去一些小树，叫做无向环套外（内）向树。虽然这题的图不一定是连通的，但是由于每一个点只会支出去一条边，所以本图是由若干个无向环套外（内）向树组成的。对于一个无向环套外（内）向树，怎么做呢？对于树的话我们可以通过树形DP（类似没有上司的舞会）的做法来做，f(i,0)表示不取 f(i,1)表示取 f(i,1)=max{f(j,0)}+w[i] f(i,0)=max{f(j,0))},max{f(j,1)}但是涉及到环呢？其实也是类似的。只不过由于首尾是有影响的，所以我们需要先强制选首选和不选各做一次DP，然后取最优值。所以首先dfs扫出该联通块内的环，打标记。对于环上每一个点进行树形DP得到答案，然后在一个环上做DP得到答案。至于如何找环的话，我们需要dfs过程中记录一下前驱。然后由于有二元环的情况，不能简单的传fa，而是需要传边的编号。
解法2：这是我在打解法1时候无意间想到的，由于n个点n条边，少一个边就变成树了，然后就可以简单的树形DP了，于是我们在dfs找环的过程中如果找到了环上的一条边，于是我们把这条边砍掉，也就是树形DP时候不走这条边，做一次DP。但是由于还是有首尾不能同时选的原因，我们可以强行选一个点或不选各做一次，也可以分别取两个点都强制不取各做一次。仔细思考一番，发现选取后者代码复杂度更低，因为如果强行取的话需要在树形DP里特判，这样就比较麻烦了。
代码：
解法1：
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #include<cstring> using namespace std; typedef long long LL; typedef pair<int,int> PII; #define mem(a,b) memset(a,b,sizeof(a)) inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=1000010; struct Edge { int u,v,next; Edge() {} Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {} }e[maxn<<1]; int n,a,ce=-1,num,first[maxn],w[maxn],pre[maxn],vis[maxn],bl[maxn],tag[maxn],top[maxn],nxt[maxn]; bool ok; LL ans,dp[2][maxn],dp2[2][maxn]; void addEdge(int a,int b) { e[++ce]=Edge(a,b,first[a]);first[a]=ce; e[++ce]=Edge(b,a,first[b]);first[b]=ce; } void dfs(int now,int eid,int id) { vis[now]=-1;bl[now]=id; for(int i=first[now];i!=-1;i=e[i].next) if(i!=eid) { if(vis[e[i].v]==-1) { int tmp=now;tag[e[i].v]=id;top[id]=e[i].v; while(tmp!=e[i].v)tag[tmp]=id,tmp=pre[tmp]; } else if(vis[e[i].v]==0)pre[e[i].v]=now,dfs(e[i].v,i^1,id); } vis[now]=1; } void treeDP(int now,int fa,int id) { dp[1][now]=w[now]; for(int i=first[now];i!=-1;i=e[i].next) if(!tag[e[i].v] && e[i].v!=fa) { treeDP(e[i].v,now,id); dp[1][now]+=dp[0][e[i].v]; dp[0][now]+=max(dp[0][e[i].v],dp[1][e[i].v]); } } void loopinit(int now,int eid,int front,int id) { if(!ok)treeDP(now,0,id); for(int i=first[now];i!=-1;i=e[i].next) if(tag[e[i].v]==id && i!=eid) { if(!ok)nxt[now]=e[i].v; if(e[i].v==front){ok=1;return;} if(!ok)loopinit(e[i].v,i^1,front,id); } } LL loopDP(int front,int id) { loopinit(front,-1,front,id); LL ret=0;mem(dp2,0); dp2[0][front]=dp[0][front]; int i=front; do { if(nxt[i]==front)break; dp2[0][nxt[i]]=max(dp2[0][i],dp2[1][i])+dp[0][nxt[i]]; dp2[1][nxt[i]]=dp2[0][i]+dp[1][nxt[i]]; i=nxt[i]; }while(i!=front); ret=max(dp2[0][i],dp2[1][i]); mem(dp2,0);dp2[1][front]=dp[1][front]; i=front; do { if(nxt[i]==front)break; dp2[0][nxt[i]]=max(dp2[0][i],dp2[1][i])+dp[0][nxt[i]]; dp2[1][nxt[i]]=dp2[0][i]+dp[1][nxt[i]]; i=nxt[i]; }while(i!=front); ret=max(ret,dp2[0][i]); ok=0; return ret; } int main() { mem(first,-1); n=read(); for(int i=1;i<=n;i++)w[i]=read(),a=read(),addEdge(i,a); for(int i=1;i<=n;i++)if(!vis[i])dfs(i,-1,++num); mem(vis,0); for(int i=1;i<=num;i++)ans+=loopDP(top[i],i); printf("%lld ",ans); return 0; }
解法2：
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #include<cstring> using namespace std; typedef long long LL; typedef pair<int,int> PII; #define mem(a,b) memset(a,b,sizeof(a)) inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=1000010; struct Edge { int u,v,next; Edge() {} Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {} }e[maxn<<1]; int n,a,ce=-1,num,first[maxn],w[maxn],vis[maxn],bl[maxn],tag[maxn],top[maxn],nxt[maxn],st,ed,es; LL ans,dp[2][maxn],dp2[2][maxn]; void addEdge(int a,int b) { e[++ce]=Edge(a,b,first[a]);first[a]=ce; e[++ce]=Edge(b,a,first[b]);first[b]=ce; } void treeDP(int now,int fa,int eid) { dp[1][now]=w[now]; for(int i=first[now];i!=-1;i=e[i].next) if(i!=eid && (i^1)!=eid && e[i].v!=fa) { treeDP(e[i].v,now,eid); dp[1][now]+=dp[0][e[i].v]; dp[0][now]+=max(dp[0][e[i].v],dp[1][e[i].v]); } } void dfs(int now,int eid,int id) { vis[now]=-1; for(int i=first[now];i!=-1;i=e[i].next) if(i!=eid) { if(vis[e[i].v]==-1)st=now,ed=e[i].v,es=i; else if(!vis[e[i].v])dfs(e[i].v,i^1,id); } vis[now]=1; } LL DP(int a,int b) { mem(dp,0); treeDP(a,0,b); return dp[0][a]; } int main() { mem(first,-1); n=read(); for(int i=1;i<=n;i++)w[i]=read(),a=read(),addEdge(i,a); for(int i=1;i<=n;i++)if(!vis[i]) { dfs(i,-1,++num); LL ret=max(DP(st,es),DP(ed,es)); ans+=ret;st=ed=0;es=-1; } printf("%lld ",ans); return 0; }
总结：
- 对于二元环一定要特殊考虑，传边的编号。
- 一定要关注代码复杂度。