【NEERC 2003】有向图破坏

【题目描述】


Alice和Bob正在玩如下的游戏。首先Alice画一个有N个顶点,M条边的有向图。然后Bob试着摧毁它。在一次操作中他可以找到图中的一个点,并且删除它所有的入边或所有的出边。

Alice给每个点定义了两个值:Wi+和Wi-。如果Bob删除了第i个点所有的入边他要给Alice付Wi+元,如果他删除了所有的出边就需要给Alice付Wi元。

找到Bob删除图中所有边需要的最小花费。

【输入格式】

输入数据描述了Alice画下的图。

输入文件的第一行有两个数N,M(1<=N<=100,1<=M<=5000)。第二行有N个整数,描述了N个点的Wi+,同样的第三行是这N个点的Wi-。所有的费用都是正数并且不超过10^6。接下来的M行每行有两个数,代表有向图中相应的一条边。

【输出格式】

输出一行一个整数,即Bob的最小花费。

【分析】

很容易想到,把每个点拆成两个点,一个控制出边,一个控制入边,保留原边后很明显的一个最小权点覆盖集,Dinic就行了。

 1 #include <cstdlib>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5 #include <queue>
6 const int maxn=500;
7 const int INF=10000*10000;
8 using namespace std;
9 struct tu
10 {
11 int c,f;
12 tu(){c=0;f=0;}
13 }maps[maxn][maxn];
14 int dist[maxn],n,m;
15
16 void Dinic();
17 bool BFS();//构建层次网络
18 int dfs(int v,int low);
19
20 int main()
21 {
22 int i;
23 //文件操作
24 freopen("destroyingthegraph.in","r",stdin);
25 freopen("destroyingthegraph.out","w",stdout);
26 memset(maps,0,sizeof(maps));
27
28 scanf("%d%d",&n,&m);//n个点,m条边
29
30 for (i=1;i<=n;i++) scanf("%d",&maps[i+n][2*n+1].c);//w+
31 for (i=1;i<=n;i++) scanf("%d",&maps[0][i].c);//w-
32
33 for (i=1;i<=m;i++)
34 {
35 int u,v;
36 scanf("%d%d",&u,&v);
37 maps[u][v+n].c=INF;
38 }
39 Dinic();
40 return 0;
41 }
42 void Dinic()
43 {
44 int flow=0;
45 while ( BFS() )
46 {
47 int temp=0;
48 if (temp=dfs(0,INF)) flow+=temp;
49 }
50 printf("%d\n",flow);
51 }
52 bool BFS()//层次网络
53 {
54 queue<int>Q;
55 int i;
56 memset(dist,-1,sizeof(dist));
57 dist[0]=0;
58 Q.push(0);
59 while (!Q.empty())
60 {
61 int u=Q.front();Q.pop();
62 for (i=0;i<=(2*n+1);i++)
63 {
64 int v=i;
65 if(maps[u][v].c-maps[u][v].f>0 && dist[v]==-1)
66 {
67 dist[v]=dist[u]+1;
68 Q.push(v);
69 }
70 }
71 }
72 return (dist[(2*n)+1]!=-1);
73 }
74 int dfs(int u,int low)
75 {
76 if (u==(2*n)+1 || low==0) return low;
77 int flow=0,f,i;
78 for (i=0;i<=(2*n)+1;i++)
79 {
80 int v=i;
81 if (maps[u][v].c>maps[u][v].f && dist[v]==dist[u]+1)
82 {
83 if (f=dfs(i,min(low,maps[u][v].c-maps[u][v].f)))
84 {
85 maps[u][v].f+=f;
86 maps[v][u].f-=f;
87 low-=f;
88 flow+=f;
89 if (low==0) break;
90 }
91 }
92 }
93 return flow;
94 }

【NEERC 2003】有向图破坏

时间: 05-15

【NEERC 2003】有向图破坏的相关文章

【网络流】【最小点权覆盖】【NEERC 2003】【POJ2125】【cogs 1575】有向图破坏

1575. [NEERC 2003][POJ2125]有向图破坏 ★★★ 输入文件:destroyingthegraph.in 输出文件:destroyingthegraph.out 简单对比 时间限制:1 s 内存限制:256 MB [题目描述] Alice和Bob正在玩如下的游戏.首先Alice画一个有N个顶点,M条边的有向图.然后Bob试着摧毁它.在一次操作中他可以找到图中的一个点,并且删除它所有的入边或所有的出边. Alice给每个点定义了两个值:Wi+和Wi-.如果Bob删除了第i个点

Windows 2003 Server 标准版启动问题解决(资源转贴)

维护的系统之一是部署在windows2003 Server标准版的服务器上,可能是由于某个应用问题,导致远程重启失败,害得我在机房呆了一早晨,可算是够折腾的.最后按照官方文档解决,刚放文档地址是:http://support.microsoft.com/kb/325375/zh-cn 内容是: 本文介绍在解决 Windows Server 2003 中的启动问题时可使用的一般过程. 成功的 Windows 启动包括以下四个阶段: 初始阶段 启动加载器阶段 内核阶段 登录阶段 如果在上述某个阶段出

Tarjan求有向图强连通详解

html,body { font-size: 15px } body { font-family: Helvetica, "Hiragino Sans GB", "微软雅黑", "Microsoft YaHei UI", SimSun, SimHei, arial, sans-serif; line-height: 1.6; margin: 0; padding: 1.33rem 1rem } h1,h2,h3,h4,h5,h6 { margin

windows 2003最完善最完美的权限及安全设置解决方案【转】

一.服务器安全设置 1. IIS6.0的安装和设置 1.1 开始菜单—>控制面板—>添加或删除程序—>添加/删除Windows组件 应用程序 ———ASP.NET(可选) |——启用网络 COM+ 访问(必选) |——Internet 信息服务(IIS)———Internet 信息服务管理器(必选) |——公用文件(必选) |——万维网服务———Active Server pages(必选) |——Internet 数据连接器(可选) |——WebDAV 发布(可选) |——万维网服务(

你为Windows Server 2003终止支持做好准备了吗?

正在使用Windows Server2003的公司业务运作正依赖着它,但7月14日微软撤回支持平台后,将会对关键任务系统产生潜在影响.我们预计,黑客会针对仍然继续使用此平台的企业用户,研究新的漏洞攻击. 建议所有企业最终迁移到一个新服务器,来不及在终止支持期限之内转移的公司,趋势科技Deep Discovery可以保护你的组织,让关键服务器继续平顺地运行.在你计划转移到较新服务器(如微软的Windows Server 2012或Azure)时,趋势科技可以帮你保护还在使用中的Windows 20

AD域的安装(在Windows Server 2003中安装Active Directory)

在Active Directory中提供了一组服务器作为身份验证服务器或登录服务器,这类服务器被称作域控制器(Domain Controller,简称DC).建立一个AD域的过程实际就是在一台运行Windows 2000 Server或运行Windows Server 2003系统的计算机上安装AD,使其成为DC的过程.安装完AD后,在DC中将网络的其他计算机加入到AD域中并创建和管理用户账户是管理AD域的重要内容.在运行Windows Server 2003(SP1)系统的服务器中安装Acti

2017 NEERC

2017 NEERC Problem A. Archery Tournament 题目描述:在二维平面上,会陆续出现一些圆,以及一些询问,询问点是否在圆内,如果是,则输出那个圆,并把那个圆删掉,否则输出\(-1\).注意:这些圆均与\(x\)轴相切,并且这些圆不会相交. solution 因为这些圆都与\(x\)轴相切,所以经过直线\(x=x'\)的圆不会超过\(log\)个.所以只要找出询问点的左右\(log\)个圆逐一判断即可. 时间复杂度:\(O(nlog10^9)\) Problem B

windows server 2003 故障排错

1.破坏MBR,并修复mbr 打开windows server 2003 将winhex文件拖到 windows server 2003 中 2.删除ntldr,并修复 原文地址:http://blog.51cto.com/guojianglong/2153373

CentOS系统启动及内核大破坏模拟实验

讲过了centos的启动流程,此时是不是想来点破坏呢?那就尽情的玩耍吧,记得在实验之前拍个快照,万一哪个环节错误恢复不回来了呢,毕竟数据无价,话不多说,开始. 一.删除伪系统根.(ramdisk文件) (1)模拟误操作删除ramdisk文件. ①模拟误删除initramfs-3.10.0-514.el7.x86_64.img文件. ②为当前正在使用的内核重新制作ramdisk文件 格式为:mkinitrd /boot/initramfs-$(uname -r).img $(uname -r) (