poj2125最小点权覆盖+找一个割集
2024-09-02 14:42:46
Destroying The Graph
Time Limit: 2000MS | Memory Limit: 65536K | |||
Total Submissions: 8503 | Accepted: 2753 | 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.
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 + 主要是找割边。
有构造出来的图知道这个是个二部图加两个源点汇点,二部图之间的连边不可能是割边(INF),所以就dfs(S)然后用vis标记,那么vis[S]一定是1,并且vis[T]一定是0.因为S,T不可能在一个集合里
那么从源点处找一下和它相连的边,看vis[]是不是0,是的话就是割边。
然后从汇点处找一下和它相连的边,看vis[]是不是1,是的话就是割边。
因为是个二部图所以不用dfs直接找一次就可以了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=;
const int INF=1e9+;
int head[N],tot,S,T;
int q[N],dis[N],n,m,Q;
bool vis[N];
struct node
{
int next,v,w;
} e[M<<];
void add(int u,int v,int w)
{
e[tot].v=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot++;
}
bool bfs()
{
memset(dis,-,sizeof(dis));
dis[S]=;
int l=,r=;
q[r++]=S;
while(l<r)
{
int u=q[l++];
for(int i=head[u]; ~i; i=e[i].next)
{
int v=e[i].v;
if(dis[v]==-&&e[i].w>)
{
q[r++]=v;
dis[v]=dis[u]+;
if(v==T) return true;
}
}
}
return false;
}
int dfs(int s,int low)
{
if(s==T||!low) return low;
int ans=low,a;
for(int i=head[s]; ~i; i=e[i].next)
{
if(e[i].w>&&dis[e[i].v]==dis[s]+&&(a=dfs(e[i].v,min(e[i].w,ans))))
{
e[i].w-=a;
e[i^].w+=a;
ans-=a;
if(!ans) return low;
}
}
if(low==ans) dis[s]=-;
return low-ans;
}
void dfs(int u){
vis[u]=;
for(int i=head[u];~i;i=e[i].next) if(!vis[e[i].v]&&e[i].w) dfs(e[i].v);
}
int a[N],b[N];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
S=,T=*n+;
int x,f,t;
memset(head,-,sizeof(head));
tot=;
for(int i=; i<=n; ++i)
{
scanf("%d",&x);
add(S,i,x);
add(i,S,);
}
for(int i=; i<=n; ++i)
{
scanf("%d",&x);
add(i+n,T,x);
add(T,i+n,);
}
while(m--)
{
scanf("%d%d",&f,&t);
add(t,f+n,INF);
add(f+n,t,);
}
int ans=;
while(bfs()) ans+=dfs(S,INF);
printf("%d\n",ans);
dfs(S);
int ct1=,ct2=;
for(int i=head[S];~i;i=e[i].next) if(!vis[e[i].v]) a[ct1++]=e[i].v;
for(int i=head[T];~i;i=e[i].next) if(vis[e[i].v]) b[ct2++]=e[i].v-n;
printf("%d\n",ct1+ct2);
for(int i=;i<ct1;++i) printf("%d +\n",a[i]);
for(int i=;i<ct2;++i) printf("%d -\n",b[i]); }
}
最新文章
- html内的空格占位
- 【jQuery api】 $.type(obj)
- Esfog_UnityShader教程_镜面反射SpecularReflection
- ioshittest的用法
- MVC的异步,Entity Framework的异步,ADO.NET的异步,
- powerdesigner逆向导出oracle数据库结构显示备注
- C#中如何查找Dictionary中的重复值
- JSNI GWT中的东东
- jsp/servlet相关技术及知识
- 读完这一篇,字符串格式化界的“白富美”(f-strings)抱回家!
- app 压力测试
- node爬虫扒小说
- 9.7 dubbo心跳机制
- java绘图合并图像AlphaComposite模式测试
- uitableview 和UISearchBar 下拉提示结合使用
- Linux导出/导入逻辑卷组信息
- PHP和MySQL实现消息队列
- AdvStringGrid 点击标题头 自动排序
- C++字符串类
- poj 3411 Paid Roads很水的DFS