题目描述
Z国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入输出格式
输入格式：
输入文件knight.in第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式：
输出文件knight.out应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
输入输出样例
说明
对于30%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 100；
对于80%的测试数据，满足N ≤ 10 000。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
很明显可以发现是dp，差不多是弱化版的没有上司的舞会，只是这题个题有环，然后就很难搞了，想了向topsort，发现没有top序，
然后通过题面发现，每个点只有一个出边，这也就是代表了，图中可能会又很多联通块，但是每个联通快最多只有一个环
所以说，我们找到每一个联通块上的环的某一条边，强行断开，一两个节点分别dp，就成了没有上司的舞会了，然后两个端点去不选这个点时的最大值加到ans里，然后坑人的地方就是，判断这条边是否被断开时，要判断这个边的编号而不是两个端点，当两个骑士互相嫌弃的时候，此时有四条边而不是两条，这样就会被卡了！
1 #include"bits/stdc++.h" 2 using namespace std; 3 #define MST(a) memset((a),0,sizeof (a)) 4 typedef long long ll; 5 6 int val[1100000]; 7 8 struct aa 9 { 10 int so,id; 11 12 }; 13 int tote=1; 14 vector<aa>v[1100000]; 15 const int nn = 1100000; 16 17 int vis[nn]; 18 ll f[nn][2]; 19 int r1,r2; 20 int del1,del2; 21 22 23 24 inline void pb(vector<aa> &t,int x) 25 { 26 t.push_back({x,++tote}); 27 } 28 int flag=0; 29 void dfs(int x,int fa) 30 { 31 vis[x]=1; 32 for (auto i:v[x]) 33 { 34 35 if(i.so==fa)continue; 36 if(!vis[i.so])dfs(i.so,x); 37 else if(vis[i.so]&&!flag) 38 { 39 r1=x;r2=i.so;flag=1; 40 del1=i.id; 41 del2=i.id^1; 42 } 43 } 44 45 } 46 47 void dfs2(int x,int fa) 48 { 49 f[x][1]=val[x]; f[x][0]=0; 50 for (auto i:v[x]) 51 { 52 int so=i.so; 53 if(so==fa)continue; 54 //if(x==r1&&i==r2||x==r2&&i==r1)continue; 55 if(i.id==del1||i.id==del2)continue; 56 dfs2(so,x); 57 f[x][1]+=f[so][0]; 58 f[x][0]+=max(f[so][1],f[so][0]); 59 } 60 } 61 ll ans=0; 62 int main() 63 { 64 int n;cin>>n; 65 66 for (int i=1;i<=n;i++) 67 { 68 int x;scanf("%d %d",&val[i],&x);pb(v[i],x);pb(v[x],i); 69 } 70 71 for (int i=1;i<=n;i++) 72 { 73 if(!vis[i]) 74 { //cout<<i<<endl; 75 ll t=0; 76 r1=r2=0; 77 flag=0; 78 dfs(i,-1); 79 80 dfs2(r1,-1); 81 t=max(t,f[r1][0]); 82 dfs2(r2,-1); 83 t=max(t,f[r2][0]); 84 ans+=t; 85 } 86 } 87 88 cout<<ans; 89 90 91 92 93 }