HDU 4940 Destroy Transportation system(2014 Multi-University Training Contest 7)

时间:2021-02-11 01:48:11

思路:无源汇有上下界可行流判定, 原来每条边转化成  下界为D  上界为 D+B   ,判断是否存在可行流即可。

为什么呢?  如果存在可行流  那么说明对于任意的 S 集合流出的肯定等于 流入的, 流出的计算的 X 肯定小于等于这个流量(X是下界之和), 计算出来的Y (上界之和)肯定大于等于 这个流量  肯定满足X<=Y。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include <iostream>
#include<climits>
using namespace std;
const int N = ;
const int M = ;
int n;
int ecnt, head[N], nx[M], to[M], va[M], cur_edge[N];
int source, target, flow, pre[N], lev[N], qu[N], sign;
void addedge(int u, int v, int w) {
to[ecnt] = v;
nx[ecnt] = head[u];
va[ecnt] = w;
head[u] = ecnt++;
}
bool bfs(int s, int t) {
std::fill(lev, lev + n, -);
sign = t;
lev[t] = ;
int st = , ed = ;
qu[ed++] = t;
while (st != ed && lev[s] == -) {
int u = qu[st++];
for (int i = head[u]; i != -; i = nx[i]) {
if (va[i ^ ] > && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
qu[ed++] = to[i];
}
}
}
return lev[s] != -;
}
void push() {
int delta = INT_MAX, u, p;
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
delta = std::min(delta, va[p]);
}
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
va[p] -= delta;
if (!va[p]) {//注意double时要改
sign = to[p ^ ];
}
va[p ^ ] += delta;
}
flow += delta;
}
void dfs(int u) {
if (u == target)
push();
else {
for (int i = cur_edge[u]; i != -; i = nx[i]) {
if (va[i] > && lev[u] == lev[to[i]] + ) {
pre[to[i]] = i;
dfs(to[i]);
if (lev[sign] > lev[u]) {
return;
}
sign = target;
}
}
lev[u] = -;
}
}
int nc, pc, tc;
int lx[M], ly[M], lv[M];
void dinic(int s, int t, int node_cnt) {
source = s;
target = t;
n = node_cnt; //construct graph flow = ;
while (bfs(source, target)) {
for (int i = ; i < n; ++i) {
cur_edge[i] = head[i];
}
dfs(source);
} }
int in[],out[];
void solve() {
int n,m;
memset(in,,sizeof(in));
memset(out,,sizeof(out));
scanf("%d%d",&n,&m);
fill(head,head+n+,-);
ecnt=;
for(int i=;i<m;++i)
{
int u,v,x,y;
scanf("%d%d%d%d",&u,&v,&x,&y);
in[v]+=x;
in[u]-=x;
addedge(u,v,y);
addedge(v,u,);
}
int s,t;
s=;t=n+;
int sum=;
for(int i=;i<=n;++i)
{
if(in[i]>)
{
sum+=in[i];
addedge(s,i,in[i]);
addedge(i,s,);
}
else
{
addedge(i,t,-in[i]);
addedge(t,i,);
}
}
dinic(s,t,t+);
if(flow==sum)puts("happy");
else puts("unhappy");
}
int main() {
int ri=,tt;
scanf("%d",&tt);
while(tt--)
{
printf("Case #%d: ",++ri);
solve();
}
return ;
}

HDU 4940 Destroy Transportation system(2014 Multi-University Training Contest 7)的更多相关文章

  1. hdu 4940 Destroy Transportation system(水过)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4940 Destroy Transportation system Time Limit: 2000/1 ...

  2. hdu 4940 Destroy Transportation system (无源汇上下界可行流)

    Destroy Transportation system Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 ...

  3. HDU 4940 Destroy Transportation system&lpar;无源汇上下界网络流&rpar;

    Problem Description Tom is a commander, his task is destroying his enemy’s transportation system. Le ...

  4. HDU 4940 Destroy Transportation system(无源汇有上下界最大流)

    看不懂题解以及别人说的集合最多只有一个点..... 然后试了下题解的方法http://blog.sina.com.cn/s/blog_6bddecdc0102uzka.html 首先是无源汇有上下界最 ...

  5. hdu 4940 Destroy Transportation system&lpar; 无源汇上下界网络流的可行流推断 &rpar;

    题意:有n个点和m条有向边构成的网络.每条边有两个花费: d:毁坏这条边的花费 b:重建一条双向边的花费 寻找这样两个点集,使得点集s到点集t满足 毁坏全部S到T的路径的费用和 > 毁坏全部T到 ...

  6. hdu4940 Destroy Transportation system&lpar;2014多校联合第七场)

    题意很容易转化到这样的问题:在一个强连通的有向图D中是否存在这样的集合划分S + T = D,从S到T集合的边权大于从T到S集合的边权. 即D(i, j)  > B(j, i) + D(j, i ...

  7. 【HDU 4940】Destroy Transportation system(无源无汇带上下界可行流)

    Description Tom is a commander, his task is destroying his enemy’s transportation system. Let’s repr ...

  8. HDU 4940(杭电更多的学校&num;7 1006) Destroy Transportation system&lpar;到处乱混)

    职务地址:pid=4940">HDU 4940 当时这个题一看就看出来了是网络流的最小割.然后就一直在想建图. .然后突然发现,应该要让T集合的数目最少,不然仅仅要有两个,那这两个的每 ...

  9. HDU4940 Destroy Transportation system&lpar;有上下界的最大流&rpar;

    Problem Description Tom is a commander, his task is destroying his enemy’s transportation system. Le ...

随机推荐

  1. ABP mapto 映射

    obj1.MapTo(obj2); obj1=>obj2: 在obj1实体里添加映射 [AutoMap(typeof(obj2))] public class obj1 { }

  2. LFI漏洞利用总结

    主要涉及到的函数 include(),require().include_once(),require_once() magic_quotes_gpc().allow_url_fopen().allo ...

  3. TCP三次握手及四次挥手详细图解(未完)

    TCP是主机对主机层的传输控制协议,提供可靠的连接服务,采用三次握手确认建立一个连接: (完成三次握手,客户端与服务器开始传送数据) 所谓三次握手(Three-way Handshake),是指建立一 ...

  4. ucGUI 12864 从打点起

      ucGUI是纯C写的的,移植需要定义点阵数,颜色数,和画点函数 以下是ucGUI 12864下的移植 基于ST7920控制的12864液晶用于字符显示很方便的,但网友说用它显示图形并不合适,原因就 ...

  5. English - allow&&num;160&semi;to&&num;160&semi;do&&num;160&semi;与&&num;160&semi;allow&&num;160&semi;doing&&num;160&semi;的区别

    英语中并没有allow to do sth这种结构,只有allow doing sth 及allow sb to do sth这两个结构. 你这样记忆可能方便一些: 1. 在主动语态中,如果allow ...

  6. C&plus;&plus;模板:Dijkstra&plus;优先队列

    #include <cstdio> #include <cstring> #include <queue> #include <utility> usi ...

  7. Codeforces 432E Square Tiling&lpar;结构体&plus;贪婪&rpar;

    题目连接:Codeforces 432E Square Tiling 题目大意:给出一个n∗m的矩阵,要求对该矩阵进行上色,用大写字母,可是每次上色的区域必须是正方形,不求相邻的上色区域不能有同样的颜 ...

  8. 洛谷-陶陶摘苹果(升级版)-BOSS战-入门综合练习1

    题目描述 Description 又是一年秋季时,陶陶家的苹果树结了n个果子.陶陶又跑去摘苹果,这次她有一个a公分的椅子.当他手够不着时,他会站到椅子上再试试. 这次与NOIp2005普及组第一题不同 ...

  9. C&num;服务器控件 IsReadOnly 和 Visibility,IsEnable 的区别

    IsReadOnly  适用于“输入.输出”类控件,比如TextBox类, 可以当做文本输入,也可以通过后台代码进行输出. 设置 IsReadOnly(只读) = true 后,该控件只允许输出,不允 ...

  10. windows10&plus;mysql8&period;0&period;11zip安装

    准备: MySQL8.0 Windows zip包下载地址:https://cdn.mysql.com//Downloads/MySQL-8.0/mysql-8.0.11-winx64.zip 环境: ...