ZOJ 2587 Unique Attack (最小割唯一性)
题意
判断一个无向图的割是否唯一
思路
错误思路：一开始想的是判断割边是否都是关键割边，那既然割边两端点能连通S、T点的边是关键边，那么只要遇到有某个边两端点不连通S or T则这条边就不是关键割边（当然要把不是割边的满流边筛掉）。这种主观臆断的naive想法是不行的，因为那个判断关键割边的条件只是个充分条件，我们没法证明它是个充要条件。 正确思路：求完最大流后在残留网络中从S点开始dfs遍历，再把残留网络反向，然后从T点开始dfs遍历，如果能遍历到所有点则最小割唯一。
代码
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 1005;
const int MAXE = 30005;
const int oo = 0x3fffffff;
struct node{
int u, v, flow;
int opp;
int next;
};
struct Dinic{
node arc[MAXE];
int vn, en, head[MAXV]; //vn点个数(包括源点汇点),en边个数
int cur[MAXV]; //当前弧
int q[MAXV]; //bfs建层次图时的队列
int path[MAXE], top; //存dfs当前最短路径的栈
int dep[MAXV]; //各节点层次
void init(int n){
vn = n;
en = 0;
mem(head, -1);
}
void insert_flow(int u, int v, int flow){
arc[en].u = u;
arc[en].v = v;
arc[en].flow = flow;
arc[en].opp = en + 1;
arc[en].next = head[u];
head[u] = en ++;arc[en].u = v;
arc[en].v = u;
arc[en].flow = flow; //反向弧
arc[en].opp = en - 1;
arc[en].next = head[v];
head[v] = en ++;
}
bool bfs(int s, int t){
mem(dep, -1);
int lq = 0, rq = 1;
dep[s] = 0;
q[lq] = s;
while(lq 0){
dep[v] = dep[u] + 1;
q[rq ++] = v;
}
}
}
return false;
}
int solve(int s, int t){
int maxflow = 0;
while(bfs(s, t)){
int i, j;
for (i = 1; i arc[path[k]].flow){
minflow = arc[path[k]].flow;
mink = k;
}
for (int k = 0; k最新文章
- ZKWeb网页框架1.2正式发布
- win10 下visual studio 2015 在调试模式下不能跟踪源文件
- background-size背景缩放
- struts2中拦截器与过滤器的区别
- Lucene 4.X 倒排索引原理与实现: (2) 倒排表的格式设计
- ZeroMQ(java)之I/O线程的实现与组件间的通信
- STRUTS2 标签 循环次数
- C++——并发编程
- centos7 下手动安装MySQL-5.6.32-1.linux_glibc2.5.x86_64.rpm-bundle
- 堆/栈的比较 以及 malloc/new动态内存的开辟
- 使用路由延迟加载 Angular 模块
- Java高新技术 Myeclipse 介绍
- P1962 斐波那契数列-题解（矩阵乘法扩展）
- 基于ROS的分布式机器人远程控制平台
- 依据ECMA规范，手写一个bind函数
- odoo 订餐系统之消息提醒
- G - 看病要排队
- 判断页面是否添加了W3C声明
- 端口报错listen eaddrinuse:::xxx
- Qt error ------ qRegisterMetaType() 跨线程信号与槽的形参携带
热门文章