洛谷P1262间谍网络
思路：
我们可以发现，不能被控制的间谍是不能被收买且不能被出卖。如果能够直接或者间接控制间谍的话，那么要么是收买入度为0的间谍，要么是几个间谍形成一个环，收买其中的最小值。 那么我们就通过可以被收买的间谍进行缩点，不断缩小给的钱的值。然后再看看有没有点没有被遍历到的点，如果有，就是有间谍不能被控制。否则，我们就将入读为0的点加起来。 注意缩点的时候，将所有的点缩成一个点，类似于并查集一样。在下面遇到这个点的时候，也要注意要用它的fa结点。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N
=1e6+10;
const int mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const double eps
=1e-8;
const double pi
=acos(-1);
using namespace std
;
struct edge
{
int u
,v
;
}e
[N
];
int head
[N
]={0},dfn
[N
],low
[N
],len
=1,num
=0,fa
[N
],v
[N
],in
[N
]={0};
int vis
[N
]={0};
stack
<int> s
;
void add(int u
,int v
)
{
e
[++len
]={head
[u
],v
};
head
[u
]=len
;
}
void tarjan(int x
)
{
int i
;
dfn
[x
]=low
[x
]=++num
;
s
.push(x
);
vis
[x
]=1;
for(i
=head
[x
];i
;i
=e
[i
].u
)
{
int y
=e
[i
].v
;
if(!dfn
[y
])
{
tarjan(y
);
low
[x
]=min(low
[y
],low
[x
]);
}
else if(vis
[y
])
low
[x
]=min(low
[x
],dfn
[y
]);
}
if(dfn
[x
]==low
[x
])
{
int pre
;
do
{
pre
=s
.top();
s
.pop();
vis
[pre
]=0;
fa
[pre
]=x
;
v
[pre
]=min(v
[pre
],v
[x
]);
}while(pre
!=x
);
}
return;
}
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int n
,m
,p
,i
,j
;
cin
>>n
>>p
;
for(i
=1;i
<=n
;i
++)
v
[i
]=inf
;
for(i
=1;i
<=p
;i
++)
{
int x
,w
;
cin
>>x
>>w
;
v
[x
]=w
;
}
cin
>>m
;
for(i
=1;i
<=m
;i
++)
{
int u
,v
;
cin
>>u
>>v
;
add(u
,v
);
}
for(i
=1;i
<=n
;i
++)
if(!dfn
[i
] && v
[i
]!=inf
)
tarjan(i
);
for(i
=1;i
<=n
;i
++)
if(!dfn
[i
])
{
cout
<<"NO"<<endl
<<i
<<endl
;
return 0;
}
int ans
=0;
cout
<<"YES"<<endl
;
for(i
=1;i
<=n
;i
++)
for(j
=head
[i
];j
;j
=e
[j
].u
)
{
int v
=e
[j
].v
;
if(fa
[i
]==fa
[v
])
continue;
in
[fa
[v
]]++;
}
for(i
=1;i
<=n
;i
++)
if(in
[i
]==0 && fa
[i
]==i
)
ans
+=v
[i
];
cout
<<ans
<<endl
;
return 0;
}
