POJ 2125 Destroying the Graph 二分图最小点权覆盖

时间:2022-10-23 07:26:10
Destroying The Graph
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8198   Accepted: 2635   Special Judge

Description

Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex. 
Alice assigns two costs to each vertex: Wi+ and Wi-. If Bob removes all arcs incoming into the i-th vertex he pays Wi+ dollars to Alice, and if he removes outgoing arcs he pays Wi- dollars. 
Find out what minimal sum Bob needs to remove all arcs from the graph.

Input

Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi+. The third line defines Wi- in a similar way. All costs are positive and do not exceed 106 . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print W --- the minimal sum Bob must have to remove all arcs from the graph. On the second line print K --- the number of moves Bob needs to do it. After that print K lines that describe Bob's moves. Each line must first contain the number of the vertex and then '+' or '-' character, separated by one space. Character '+' means that Bob removes all arcs incoming into the specified vertex and '-' that Bob removes all arcs outgoing from the specified vertex.

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5
3
1 +
2 -
2 +

Source

Northeastern Europe 2003, Northern Subregion

【题意】:

N个点M条边的有向图,给出如下两种操作。
删除点i的所有出边,代价是Ai。
删除点j的所有入边,代价是Bj。
求最后删除图中所有的边的最小代价。

其实就是二分图最小点权覆盖。

定义:从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。

//最小点权覆盖就是求最小割(证明可参考胡伯涛论文“最小割模型在信息学竞赛中的应用”)。

【题解】:

拆点。n个点拆成2n个点(左右各n个,i与(i+n)对应,之间连容量INF的边),S和i连容量为Ai的边,(i+n)与T之间连容量为Bi的边,求最小割即可

这样做为什么对呢?

当一条边存在的条件就是网络中还存在从S到T的非满流边!

方案输出不多说。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register
#define inf 0x3f3f3f3f
using namespace std;
int read(){
R int x=;bool f=;
R char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
}
const int N=1e5+;
struct node{
int v,next,cap,flow;
}e[N<<];int tot=;
struct data{
int x,op,val;
bool operator <(const data &a)const{
return val==a.val?x<a.x:val<a.val;
}
}record[N];
int n,m,cs,cc,S,T,a[N],b[N],cur[N],head[N],dis[N],q[N*];
bool mark[N];
void add(int x,int y,int z){
e[++tot].v=y;e[tot].next=head[x];e[tot].cap=z;e[tot].flow=;head[x]=tot;
e[++tot].v=x;e[tot].next=head[y];e[tot].cap=;e[tot].flow=;head[y]=tot;
}
bool bfs(){
int h=,t=;
memset(dis,-,sizeof(dis));
dis[S]=;q[]=S;
while(h!=t){
int x=q[++h];
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(dis[v]==-&&e[i].cap>e[i].flow){
dis[v]=dis[x]+;
q[++t]=v;
}
}
}
return dis[T]!=-;
}
int dfs(int x,int f){
if(x==T||!f) return f;
int used=,f1;
for(int &i=cur[x];i;i=e[i].next){
if(dis[x]+==dis[e[i].v]&&(f1=dfs(e[i].v,min(f,e[i].cap-e[i].flow)))>){
e[i].flow+=f1;e[i^].flow-=f1;
used+=f1;f-=f1;
if(!f) break;
}
}
return used;
}
int dinic(){
int ans=;
while(bfs()){
for(int i=S;i<=T;i++) cur[i]=head[i];
ans+=dfs(S,0x7fffffff);
}
return ans;
}
void dfs_cut(int x){
if(x==T) return ;
mark[x]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].v,val,op;
if(!mark[v]){
if(e[i].cap==e[i].flow){
if(x!=S){
if(x>n) op=,val=b[x-n];
else op=,val=a[x];
record[++cc].x=x;record[cc].op=op;record[cc].val=val;
}
if(v!=T){
if(v>n) op=,val=b[v-n];
else op=,val=a[v];
record[++cc].x=v;record[cc].op=op;record[cc].val=val;
}
}
dfs_cut(v);
} }
}
int main(){
n=read();m=read();
S=;T=n<<|;
for(int i=;i<=n;i++) a[i]=read(),add(S,i,a[i]);
for(int i=;i<=n;i++) b[i]=read(),add(i+n,T,b[i]);
for(int i=,x,y;i<=m;i++) x=read(),y=read(),add(x,y+n,inf);
printf("%d\n",dinic());
dfs_cut(S);
for(int i=;i<=n;i++){
if(!mark[i]) cs++;
if(mark[i+n]) cs++;
}
printf("%d\n",cs);
for(int i=;i<=cc;i++) if(record[i].x>n) record[i].x-=n;
sort(record+,record+cc+);
for(int i=;i<=cs;i++){
int &x=record[i].x,&y=record[i].op;
printf("%d ",x);putchar(y?'+':'-');printf("\n");
}
return ;
}

输出方案WA到挺的代码

//AC代码(终于改出来了)
#include<cstdio>
#include<iostream>
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=1e5+;
const int inf=0x7fffffff;
struct node{
int v,next,cap;
}e[N*];int tot=;
int n,m,p,S,T,a[N],b[N],head[N],dis[N],q[N*];
bool vis[N];
void add(int x,int y,int z){
e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].cap=;e[tot].next=head[y];head[y]=tot;
}
bool bfs(){
for(int i=S;i<=T;i++) dis[i]=inf;
int h=,t=;q[t]=S;dis[S]=;
while(h!=t){
int x=q[++h];
for(int i=head[x],v;i;i=e[i].next){
if(e[i].cap&&dis[v=e[i].v]>dis[x]+){
dis[v]=dis[x]+;
if(v==T) return ;
q[++t]=v;
}
}
}
return ;
}
int dfs(int x,int f){
if(x==T) return f;
int used=,t;
for(int i=head[x],v;i;i=e[i].next){
if(e[i].cap&&dis[v=e[i].v]==dis[x]+){
t=dfs(v,min(f,e[i].cap));
e[i].cap-=t;e[i^].cap+=t;
used+=t;f-=t;
if(!f) return used;
}
}
if(!used) dis[x]=;
return used;
}
int dinic(){
int res=;
while(bfs()) res+=dfs(S,inf);
return res;
}
void dfs_cut(int x){
vis[x]=;
for(int i=head[x],v;i;i=e[i].next){
if(!e[i].cap||vis[v=e[i].v]) continue;
dfs_cut(v);
}
}
int main(){
n=read();m=read();S=;T=n<<|;
for(int i=;i<=n;i++) a[i]=read(),add(i+n,T,a[i]);
for(int i=;i<=n;i++) b[i]=read(),add(S,i,b[i]);//边是反的,dfs_cut是正的。WA*1
for(int i=,x,y;i<=m;i++) x=read(),y=read(),add(x,y+n,inf);
printf("%d\n",dinic());
dfs_cut(S);
for(int i=;i<=n;i++){
if(!vis[i]) p++;
if(vis[i+n]) p++;
}
printf("%d\n",p);
for(int i=;i<=n;i++){
if(!vis[i]) printf("%d -\n",i);
if(vis[i+n]) printf("%d +\n",i);
}
return ;
}

POJ 2125 Destroying the Graph 二分图最小点权覆盖的更多相关文章

  1. POJ 2125 Destroying The Graph &lpar;二分图最小点权覆盖集&plus;输出最小割方案&rpar;

    题意 有一个图, 两种操作,一种是删除某点的所有出边,一种是删除某点的所有入边,各个点的不同操作分别有一个花费,现在我们想把这个图的边都删除掉,需要的最小花费是多少. 思路 很明显的二分图最小点权覆盖 ...

  2. POJ 2125 Destroying The Graph 二分图 最小点权覆盖

    POJ2125 题意简述:给定一个有向图,要通过某些操作删除所有的边,每一次操作可以选择任意一个节点删除由其出发的所有边或者通向它的所有边,两个方向有不同的权值.问最小权值和的解决方案,要输出操作. ...

  3. poj 2125 Destroying The Graph (最小点权覆盖)

    Destroying The Graph http://poj.org/problem?id=2125 Time Limit: 2000MS   Memory Limit: 65536K       ...

  4. POJ2125 Destroying The Graph 二分图 &plus; 最小点权覆盖 &plus; 最小割

    思路来源:http://blog.csdn.net/lenleaves/article/details/7873441 求最小点权覆盖,同样求一个最小割,但是要求出割去了那些边, 只要用最终的剩余网络 ...

  5. POJ2125 Destroying The Graph(二分图最小点权覆盖集)

    最小点权覆盖就是,对于有点权的有向图,选出权值和最少的点的集合覆盖所有的边. 解二分图最小点权覆盖集可以用最小割: vs-X-Y-vt这样连边,vs和X部点的连边容量为X部点的权值,Y部和vt连边容量 ...

  6. POJ - 2125 Destroying The Graph &lpar;最小点权覆盖&rpar;

    题意:给一张图,现在要删去所有的边,删去一个点的所有入边和所有出边都有其对应\(W_{i+}\)和\(W_{i-}\).求删去该图的最小花费,并输出解 分析:简而言之就是用最小权值的点集去覆盖所有的边 ...

  7. poj 3308 Paratroopers(二分图最小点权覆盖)

    Paratroopers Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8954   Accepted: 2702 Desc ...

  8. POJ3308 Paratroopers(最小割&sol;二分图最小点权覆盖)

    把入侵者看作边,每一行每一列都是点,选取某一行某一列都有费用,这样问题就是选总权最小的点集覆盖所有边,就是最小点权覆盖. 此外,题目的总花费是所有费用的乘积,这时有个技巧,就是取对数,把乘法变为加法运 ...

  9. POJ 3308 Paratroopers(最大流最小割の最小点权覆盖)

    Description It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the ...

随机推荐

  1. JAVA GUI编程学习笔记目录

    2014年暑假JAVA GUI编程学习笔记目录 1.JAVA之GUI编程概述 2.JAVA之GUI编程布局 3.JAVA之GUI编程Frame窗口 4.JAVA之GUI编程事件监听机制 5.JAVA之 ...

  2. tjkd-html

    <div class="result-item"> <div class="kd-item"> <div class=" ...

  3. FusionCharts简单教程&lpar;三&rpar;-----FusionCharts的基本属性

          通过前面两章的讲解我们可以制作出简单的图像,但是有时候我们需要对图像进行一个精确的规划,比如设置背景颜色.设置提示信息.设置间隔颜色等等,这时就需要我们对FusionCharts的细节有比 ...

  4. 解决python &quot&semi;Non-ASCII character&quot&semi;错误

    原文http://jingyan.baidu.com/article/219f4bf7d04887de442d3899.html 1.出现问题的原因:程序中的编码错误,python默认是acii模式, ...

  5. 5种IO模型

    Unix下可用的5种I/O模型分别是: 阻塞IO 非阻塞IO IO复用(select和poll) 信号驱动式IO(SIGIO) 异步IO(POSIX的aio系列函数)   阻塞式I/O模型:      ...

  6. AutoResetEvent 类的使用说明

    AutoResetEvent 类 官方描述:通知正在等待的线程已发生事件 命名空间:System.Threading 程序集:mscorlib 继承于:System.Threading.WaitHan ...

  7. Django Haystack 全文检索与关键词高亮

    Django Haystack 简介 django-haystack 是一个专门提供搜索功能的 django 第三方应用,它支持 Solr.Elasticsearch.Whoosh.Xapian 等多 ...

  8. Ajax 传包含集合的JSON

    通过ajax给后台传json对象,当json中含对象集合时,如 $.ajax({ url : , type : "POST", dataType : "json&quot ...

  9. Zookeeper 工作流

    一旦ZooKeeper集合启动,它将等待客户端连接.客户端将连接到ZooKeeper集合中的一个节点.它可以是leader或follower节点.一旦客户端被连接,节点将向特定客户端分配会话ID并向该 ...

  10. tarnado源码解析系列一

    目录 tarnado tarnado源码安装 tarnado测试程序 application类的解析 一. tarnado简介 最近在学习Python,无意间接触到的tarnado,感觉tarnado ...