题目描述
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 }