洛谷P1262:https://www.luogu.org/problemnew/show/P1262

思路

一看题目就知道是强连通分量缩点

当图中有强连通分量时 将其缩点

我们可以用dfn数组判断是否可以达到所有人都可以控制

到最后图中可能有如下2种情况

First 整个图为一个强连通分量 ans即是能贿赂的最小值

Second 当图中有链时 贿赂链的第一个人即可取得最小值

代码

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 3010
#define INF 1e9+7
int n,r,p,top,num,cnt,col,ans;
int money[maxn],h[maxn*],de[maxn],st[maxn],dfn[maxn],low[maxn],co[maxn],minn[maxn];
bool vis[maxn];
struct Edge
{
int to;
int next;
}e[maxn*];
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void read()
{
cin>>n>>p;
for(int i=;i<=n;i++)
minn[i]=money[i]=INF;//初始化
for(int i=;i<=p;i++)
{
int x,y;
cin>>x>>y;
money[x]=y;
}
cin>>r;
for(int i=;i<=r;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
}
}
void Tarjan(int u)
{
dfn[u]=low[u]=++num;
st[++top]=u;
vis[u]=;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else
if(vis[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
col++;
while(st[top+]!=u)
{
co[st[top]]=col;
vis[st[top]]=;
minn[col]=min(minn[col],money[st[top]]);//计算每个强连通分量中的最小花费
top--;
}
}
}
int main()
{
read();
for(int i=;i<=n;i++)
if(!dfn[i]&&money[i]!=INF) Tarjan(i);//能被贿赂的人才可以缩点
for(int i=;i<=n;i++)
if(!dfn[i])//如果dfn为0说明没有被控制
{
cout<<"NO"<<endl<<i;
return ;
}
for(int i=;i<=n;i++)//统计入度
for(int j=h[i];j;j=e[j].next)
if(co[i]!=co[e[j].to]) de[co[e[j].to]]++;
for(int i=;i<=col;i++)//如果入度为0 即是一条链
if(!de[i]) ans+=minn[i];
cout<<"YES"<<endl<<ans;
}

最新文章

  1. 使用Logstash进行日志分析
  2. doxygen的使用(一)配置并生成文档
  3. 实现Base64加密解密
  4. python 获取文件夹大小
  5. C# Out 传值
  6. 谈谈“色彩空间表示方法”——RGB、YUY2、YUYV、YVYU、UYVY、AYUV
  7. 求两个数的最大公约数(Java)
  8. 2016.04.09 使用Powerdesigner进行创建数据库的概念模型并转为物理模型
  9. (Problem 33)Digit canceling fractions
  10. hibernate---关联关系的 crud_cascade_fetch
  11. PHP四种基本排序算法
  12. 移动端的一些常用meta标签
  13. 上传图片截图预览控件不显示cropper.js 跨域问题
  14. vue router history模式开发ngnix配置
  15. A - 地精部落 (DP)
  16. 一个获取本机ip地址的正则
  17. vue中的前置守卫
  18. 如何用移动硬盘安装win7 系统
  19. [转]Extending the User Interface in Outlook 2010
  20. Visual Studio 2015 正式版镜像下载(含专业版/企业版KEY)

热门文章

  1. BJFU 1549 ——Candy——————【想法题】
  2. github不支持tlsv1.1后, 出现SSL connect error
  3. Flask 框架理解(一)
  4. Visual Studio 安装OpenCV及问题总结
  5. geth
  6. ActiveReport报表更改连接字符串及参数
  7. Thrift笔记(四)--Thrift client源码分析
  8. 多线程篇四:ThreadLocal实现线程范围内变量共享
  9. Csharp:TinyMCE HTML Editor in .NET WindowsForms
  10. JavaScirpt(JS)的this细究