题面
一句话题意：一个图，有些点可以有一定代价被“买”，“被买”这个点能到的点能免费“被买”，求最少的代价，或者输出最小的不能被买的点。
思路
用Tarjin对一开始能“被买”的点作为起点，进行缩点，即tarjin(k)，k是能被买的点。
for(int i=1; i<=n; i++) if(!dfn[i]&&pr[i]<1e9) tarjin(i);
Tarjin后，用循环过一遍所有点，如果有点没有被访问（即dfn=0），即是“NO”，并输出该点即可。
for(int i=1; i<=n; i++)
if(!dfn[i])
{
printf("NO\n%d\n",i);
return 0;
}
否则把所有强连通分量跑一边，先重新构图求入度，再在入度为0的强连通分量中找“代价”最小的点，加到答案里。
for(int i=1; i<=n; i++)
for(int j=head[i]; j; j=a[j].nxt)
if(co[i]!=co[a[j].to]) cntt[co[a[j].to]]++;
for(int i=1; i<=num; i++) if(!cntt[i]) ans+=p[i];
最后到了Tarjin
Tarjin中我只多了一句话，就是顺便统计一下一个强连通分量中代价最小的一个。
void tarjin(int k)
{
low[k]=dfn[k]=++tot,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num,p[num]=pr[k];
while(st.top()!=k) co[st.top()]=num,p[num]=min(p[num],pr[st.top()]),st.pop();
st.pop();
}
}
代码
没加注释，详细请看前面思路。
#include <bits/stdc++.h>
using namespace std;
int n,x,y,ans,pr[3005],m,ansm=1e9;
struct node
{
int to,nxt;
} a[8005];
int cnt,head[3005],cntt[3005];
int dfn[3005],low[3005],co[3005],num,tot;
int p[3005];
void add(int x,int y)
{
a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
stack<int> st;
void tarjin(int k)
{
low[k]=dfn[k]=++tot,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num,p[num]=pr[k];
while(st.top()!=k) co[st.top()]=num,p[num]=min(p[num],pr[st.top()]),st.pop();
st.pop();
}
}
int main()
{
scanf("%d%d",&n,&m),memset(pr,0x3f,sizeof(pr));
for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),pr[x]=y;
scanf("%d",&m);
for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),add(x,y);
for(int i=1; i<=n; i++) if(!dfn[i]&&pr[i]<1e9) tarjin(i);
for(int i=1; i<=n; i++) if(!dfn[i])
{
printf("NO\n%d\n",i);
return 0;
}
for(int i=1; i<=n; i++)
for(int j=head[i]; j; j=a[j].nxt)
if(co[i]!=co[a[j].to]) cntt[co[a[j].to]]++;
for(int i=1; i<=num; i++) if(!cntt[i]) ans+=p[i];
printf("YES\n%d\n",ans);
return 0;
}
小结
首先是思路的问题，其实我想了很久，也改了几次，最终确定了这一个。
其次是代码的问题，注意i和j之间的区别（我老是把co[i]写成co[j]）。
最后是码风，我喜欢压行，又受于编程软件的限制，所以码风不三不四的，不喜勿喷。
完结撒花！
