二分图最大匹配的一些证明,如何驾驭你的关系网

全文预警:本篇复杂指数五颗星。

①最小路径覆盖: 

给定有向图G=(V,E)。设P
是G 的一个简单路(顶点不相交)的集合。如果V 中每个顶点恰好在P
的一条路上,则称P是G 的一个路径覆盖。P 中路径可以从V
的任何一个顶点开始,长度也是任意的,特别地,可以为0。G 的最小路径覆盖是G
的所含路径条数最少的路径覆盖。 

路径覆盖和二分图匹配的关系:最小路径覆盖=|G|-最大匹配数

上述公式中最大匹配数是这样来的: 

对于G中每一个节点x,建立节点x1,x2。若x-
>y存在边,则x1与y2之间连一条无向边,求这个二分图的最大匹配数即可。

证明如下:

首先,若最大匹配数为0,则二分图中无边,也就是说有向图G中不存在边,那么

显然:最小路径覆盖=|G|-最大匹配数=|G|-0=|G|。 

若此时增加一条匹配边x1–y2,则在有向图|G|中,x、y在同一条路径上,最小路径覆盖数减少一个。

继续增加匹配边,每增加一条,最小路径覆盖数减少一个,则公式:最小路径覆盖=|G|-最大匹配数得证。

 

从现在开始把每一个我觉得对我来说有新意的图论题目汇集下来

新浦京www81707con,灵魂宝石 bzoj 2663,bzoj2663

灵魂宝石(1s 128MB)soulgem

【问题描述】 

“作为你们本体的灵魂,为了能够更好的运用魔法,被赋予了既小巧又安全的外形······” 

我们知道,魔法少女的生命被存放于一个称为灵魂宝石(Soul
Gem)的装置内。而有时,当灵魂宝石与躯体的距离较远时,魔法少女就无法控制自己的躯体了。

在传说中,魔法少女Abel仅通过推理就得到了这个现象的一般法则,被称为Abel定理:存在宇宙常量R(是一个非负实数,或正无穷),被称为灵魂宝石常量,量纲

为空间度量(即:长度)。如果某个魔法少女的灵魂宝石与她的躯体的距离严格超过R,则她一定无法控制自己的躯体;如果这个距离严格小于R,则她一定可以控

制自己的躯体。(这里的距离指平面的 Euclid距离。) 

注意:该定理不能预言距离刚好为R的情形。可能存在魔法少女A和B,她们离自己的灵魂宝石的距离都恰好为R,但是A可以控制自己的躯体,而B不可以。

现在这个世界上再也没有魔法少女了,但是我们却对这个宇宙常量感兴趣。我们只能通过之前的世界遗留下来的数据来确定这个常量的范围了。

每一组数据包含以下信息: 

二分图最大匹配的一些证明,如何驾驭你的关系网。一共有N个魔法少女及她们的灵魂宝石,分别编号为1-N。

这N个魔法少女所在的位置是(Xi, Yi)。 

这N个灵魂宝石所在的位置是(xi, yi)。 

此时恰好有 K个魔法少女能够控制自己的躯体。

1.我们认为这个世界是二维的 Euclid 空间。

2.魔法少女与灵魂宝石之间的对应关系是未知的。

3.我们不知道是具体是哪 K个魔法少女能够控制自己的躯体。

根据以上信息,你需要确定灵魂宝石常量 R可能的最小值 Rmin 和最大值Rmax。

【输入格式】

第一行包两个整数:N、K。 
接下来N行,每行包含两个整数:Xi,Yi,由空格隔开。 
再接下来N行,每行包含两个整数:xi,yi,由空格隔开。 

【输出格式】

输出两个量:Rmin、Rmax,中间用空格隔开。 
Rmin 一定是一个非负实数,四舍五入到小数点后两位。 
Rmax 可能是非负实数,或者是正无穷: 
如果是非负实数,四舍五入到小数点后两位; 
如果是正无穷,输出“+INF”(不包含引号)。

【输入样例】

2 1

1 0

4 0

0 0

4 4

【输出样例】

1.00 5.00

【数据范围】

对于100%的数据: 

1 ≤ N ≤ 50,0 ≤ K ≤ N,-1000 ≤ xi,yi,Xi,Yi ≤ 1000。


 

题解:

主要算法:二分图匹配 or 网络流;二分;

题意:对于n个人与n个宝石,每个人需要各自匹配一1颗与其距离小于k的宝石,距离等于k的宝石可以自由选择是否匹配,求k的最小值与最大值

那么最小值可以很容易想到二分,连接所有距离小于k的边,用二分图匹配检验,则为用最大匹配数求最小值

然而最大值并不能直接像最小值一样求解,因为二分图求的是最大匹配,这一点模拟样例就可以得到

于是考虑一点小小的转化

最大值的检验中,我们将距离大于等于k的边相连

那么二分图匹配跑出的结果就是最大不匹配数

总个数减去最大不匹配数即为最小匹配数

只要我们用利用最小匹配数就能求出最大值

 

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cstdio>
  6 #include<cmath>
  7 using namespace std;
  8 struct shape
  9 {
 10     double x, y;
 11 };
 12 int n, k;
 13 double l, r;
 14 double ans;
 15 int my[233];
 16 shape a[233];
 17 bool vis[233];
 18 int tot, to[10233], nex[10233], fir[233];
 19 inline double Dis(shape x, shape y)
 20 {
 21     return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
 22 }
 23 inline void Ins(int x, int y)
 24 {
 25     nex[++tot] = fir[x];
 26     fir[x] = tot;
 27     to[tot] = y;
 28 }
 29 bool Find(int u)
 30 {
 31     for(int i = fir[u]; i; i = nex[i])
 32     {
 33         int v = to[i];
 34         if(!vis[v])
 35         {
 36             vis[v] = true; 
 37             if(!my[v] || Find(my[v]))
 38             {
 39                 my[v] = u;
 40                 return true;
 41             }
 42         }
 43     }
 44     return false;
 45 }
 46 inline bool Checkmi(double x)
 47 {
 48     tot = 0;
 49     for(int i = 1; i <= n; ++i) my[i + n] = fir[i] = 0;
 50     for(int i = 1; i <= n; ++i)
 51         for(int j = n + 1; j <= n + n; ++j)
 52             if(Dis(a[i], a[j]) <= x)
 53                 Ins(i, j);
 54     int sum = 0;
 55     for(int i = 1; i <= n; ++i)
 56     {
 57         for(int j = 1; j <= n; ++j)
 58             vis[j + n] = false;
 59         if(Find(i)) ++sum;
 60     }
 61     if(sum < k) return true;
 62     return false;
 63 }
 64 inline bool Checkma(double x)
 65 {
 66     tot = 0;
 67     for(int i = 1; i <= n; ++i) my[i + n] = fir[i] = 0;
 68     for(int i = 1; i <= n; ++i)
 69         for(int j = n + 1; j <= n + n; ++j)
 70             if(Dis(a[i], a[j]) >= x)
 71                 Ins(i, j);
 72     int sum = 0;
 73     for(int i = 1; i <= n; ++i)
 74     {
 75         for(int j = 1; j <= n; ++j)
 76             vis[j + n] = false;
 77         if(Find(i)) ++sum;
 78     }
 79     if(sum < n - k) return false;
 80     return true;
 81 }
 82 int main()
 83 {
 84 //    freopen("soulgem.in", "r", stdin), freopen("soulgem.out", "w", stdout);
 85     scanf("%d%d", &n, &k);
 86     for(int i = 1; i <= n + n; ++i)
 87         scanf("%lf %lf", &a[i].x, &a[i].y);
 88     l = 0, r = 3666;
 89     for(int i = 1; i <= 38; ++i)
 90     {
 91         double mi = (l + r) / 2.0;
 92         if(Checkmi(mi)) l = mi;
 93         else ans = mi, r = mi;
 94     }
 95     printf("%.2lf ", ans);
 96     ans = 3666;
 97     l = 0, r = 3666;
 98     for(int i = 1; i <= 38; ++i)
 99     {
100         double mi = (l + r) / 2.0;
101         if(Checkma(mi)) ans = mi, l = mi;
102         else r = mi;
103     }
104     if(fabs(ans - 3666) <= 0.001) printf("+INF");
105     else printf("%.2lf", ans);
106 }

 

bzoj 2663,bzoj2663
灵魂宝石(1s128MB)soulgem 【问题描述】
“作为你们本体的灵魂,为了能够更好的运用魔法,被赋予了既小巧又安…

“复杂网络”是个啥?

你看过琅琊榜吗?这部作品有两个特点:帅哥特别多,帅哥之间的关系特别复杂。像这样的人际关系网络就是一个简单的复杂网络。类似的,交通运输网络、电力系统网络、微博上的相互关注、Facebook上的好友关系,这些也都是典型的复杂网络。

新浦京www81707con 1琅琊榜中的人际关系网络。图片来源:www.anyv.net

关于复杂网络的研究兴起于20世纪末期,很快就被广泛地应用于各个领域。复杂网络既是对数据的一种表现形式,也是一种研究的手段。在研究复杂网络的系统图示里,系统的各个组成部分叫做节点;部分之间的相互关系叫做连边。研究复杂网络的重要目的是为了控制网络,趋利避害。比如,在癌症治疗的时候,我们就希望通过外界控制将某些疾病状态的细胞转换为健康状态的细胞,达到治愈的目的。

新浦京www81707con 2复杂网络的基本要素。供图:成慧敏
张忠元。

②最小点覆盖

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

最小点覆盖数 =
最大匹配数

证明:转载自:Matrix67

ps:今天发现了一个非常重要的常识我之前竟然一直没有注意到:对一个图第一遍跑最大流结果是最大流,如果还继续跑第二遍,结果会是0,很容易理解的地方,我竟然一直没有注意到。

复杂网络如何控制?

二分图最大匹配的König定理及其证明 

 

    如果你看不清楚第二个字母,下面有一个大号字体版本:

二分图最大匹配的König定理及其证明

    本文将是这一系列里最短的一篇,因为我只打算把König定理证了,其它的废话一概没有。
    以下五个问题我可能会在以后的文章里说,如果你现在很想知道的话,网上去找找答案:
    1.
什么是二分图;
    2.
什么是二分图的匹配;
    3.
什么是匈牙利算法;()
    4.
König定理证到了有什么用;
    5.
为什么o上面有两个点。

    König定理是一个二分图中很重要的定理,它的意思是,一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖,我也在这里说一下:假如选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖所有的边。比如,下面这个图中的最大匹配和最小点覆盖已分别用蓝色和红色标注。它们都等于3。这个定理相信大多数人都知道,但是网络上给出的证明并不多见。有一些网上常见的“证明”明显是错误的。因此,我在这里写一下这个定理的证明,希望对大家有所帮助。

新浦京www81707con 3

    假如我们已经通过匈牙利算法求出了最大匹配(假设它等于M),下面给出的方法可以告诉我们,选哪M个点可以覆盖所有的边。
    匈牙利算法需要我们从右边的某个没有匹配的点,走出一条使得“一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现”的路(交错轨,增广路)。但是,现在我们已经找到了最大匹配,已经不存在这样的路了。换句话说,我们能寻找到很多可能的增广路,但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号:从右边的所有没有匹配过的点出发,按照增广路的“交替出现”的要求可以走到的所有点(最后走出的路径是很多条不完整的增广路)。那么这些点组成了最小覆盖点集:右边所有没有打上记号的点,加上左边已经有记号的点。看图,右图中展示了两条这样的路径,标记了一共6个点(用
“√”表示)。那么,用红色圈起来的三个点就是我们的最小覆盖点集。
    首先,为什么这样得到的点集点的个数恰好有M个呢?答案很简单,因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的,那么它早就当成起点被标记了;如果左边的哪个点是没有匹配过的,那就走不到它那里去(否则就找到了一条完整的增广路)。而一个匹配边又不可能左端点是标记了的,同时右端点是没标记的(不然的话右边的点就可以经过这条边到达了)。因此,最后我们圈起来的点与匹配边一一对应。
    其次,为什么这样得到的点集可以覆盖所有的边呢?答案同样简单。不可能存在某一条边,它的左端点是没有标记的,而右端点是有标记的。原因如下:如果这条边不属于我们的匹配边,那么左端点就可以通过这条边到达(从而得到标记);如果这条边属于我们的匹配边,那么右端点不可能是一条路径的起点,于是它的标记只能是从这条边的左端点过来的(想想匹配的定义),左端点就应该有标记。
    最后,为什么这是最小的点覆盖集呢?这当然是最小的,不可能有比M还小的点覆盖集了,因为要覆盖这M条匹配边至少就需要M个点(再次回到匹配的定义)。

 

由于目前基本只会网络流,就先来网络流的吧:

用最小的成本控制整个网络

我们先从一个简单的例子开始。胖虎要举办生日聚会,希望来的朋友越多越好。哆啦A梦说大雄去我就去,大雄说静香去我就去。请问胖虎如何让静香、大雄、哆啦A梦3人都去参加聚会呢?

胖虎当然可以挨个搞定静香、大雄和哆啦A梦。不过,只搞定静香显然也可以达到同样的效果。因为这三个人之间存在相互联系。合理利用这种联系,就可以“牵一发以动全身”。就像一辆汽车,无论内部构造多精巧,系统多复杂,我们只需要管好方向盘和刹车等几个关键点就能达到控制的目的。

在复杂网络中也存在类似的情况。我们当然可以对网络中数量众多的节点分别进行控制。但这种控制无疑需要投入大量的时间和精力。而且,当网络增大到一定规模时,这种控制甚至根本不可行。所以,如何找到复杂网络中的“静香”,通过控制一个,或少数几个关键节点,实现对整个网络的控制,以最少的投入达到最大的效果,这是研究复杂网络想要解决的问题之一。

新浦京www81707con 4胖虎通过“控制”静香就可以达到邀请全部三人到生日聚会的目的。供图:成慧敏
张忠元。

那么,如何以最少的投入来控制整个复杂网络呢?这就需要解决两个问题:什么样的网络是可控的?以及,如何找到数量最少,又能控制这个网络的节点?

③最大独立集=总数-最小覆盖集证明:

(摘自:)

新浦京www81707con 5

  上图,我们用两个红色的点覆盖了所有边。我们证明的前提条件是已经达到最小覆盖。

即条件1.已经覆盖所有边,条件2.所用的点数最小

  首先我们来证明蓝色点组成的是一个独立集:如果有两个蓝色点间有边相连,那么这条

边则没有被覆盖,则与条件1矛盾。因此是独立集。

  再来证明这个独立集最大:
如果我们要再增加这个独立集中的点,则需要把某个红点变

成蓝点。而由最小覆盖数=最大匹配数的证明我们知道,每一个红点是最大匹配中的一

个匹配点,也就是说每个红点至少连接了一条边。因此当我们将某个红点变成蓝点

时,我们需要牺牲的蓝点的个数是大于等于1的。也就是说,我们最多只能找到数量相等

的其他独立集,而无法找到数量更大的。因此蓝色点集必定为最大独立集。
蓝色点数 =

总点数 –
红色点数,即最大独立集=总数-最小覆盖集。

 

由上述定理,同理可知: 

最大独立集+最小点权覆盖=总权值。

 又∵最小点权覆盖=最小割*** ***

  
 ∴最大独立集=最小割。

 

1.hdu2883

知己知彼,百战不殆:什么样的网络是可控的?

想要控制一个复杂网络,先得确认这个网络是否可控。什么样的网络是可控的呢?网络可控的意思就是借助外力作用(对某些节点输入控制信号),我们能够独立地控制这个网络中的每个节点。这句话包含了两个含义:

1. 我们可以控制网络中每个节点。只要网络中有一个节点不受控制,那么这个网络就没有被控制住。比如下面这幅图示的网络中,如果我们只对节点1输入控制信号,节点3就不受控制,我们也就无法控制整个网络。所以要想控制住这个网络仅仅对节点1施加外力是不够的,还需要对节点3也施加一个外力。

新浦京www81707con 6
2. 我们可以独立地控制每个节点。看下面的示意图。在这个网络里,每当我们对节点1施加控制,节点1的变化一定会同时引起节点2和节点3的变化。假设我们的目的是想改变节点2,同时保持节点3不变的话,在这样的网络中是永远也无法实现的。总结成规律,就是,如果网络里有两个节点受到且仅受到同一个节点的控制,那么这两个节点就不是被独立地控制的。

新浦京www81707con 7

原理介绍完了,咱们来举一个例子。请问,在下面三种网络结构中,哪个控制源能成功控制全网?

新浦京www81707con 8节点间带箭头的连边代表控制关系。图a红色节点“3”为不可达节点;图b红色节点“2”包含膨胀结构;图c为既不包含不可达节点也不包含膨胀节点的“仙人掌”结构。供图:成慧敏
张忠元。

答案是,C。

在网络结构(a)中,控制源控制节点1,节点1控制节点2,但是节点2无法控制节点3,节点3处于控制不可达的状态,因此信号源无法控制全网。

在网络结构(b)中,节点3和节点4同时受到节点2
的控制,无法被独立控制,因此信号源无法控制全网。

与图(b)相比,网络结构(c)中,节点4和节点5可以互相控制,套用刚才总结的规律,此时,节点3和节点4不再受到且仅受到一个节点的控制——节点4不仅受到来自节点2的控制,还受到来自节点5的控制。
因此,在(c)结构中,控制源可以通过控制节点1达到独立地控制每一个节点,也就是控制全网的目的。

题意: 有一个烧烤机,每次最多能烤 m 块肉,现在有 n
个人来买烤肉,每个人到达时间为 si,离开时间为 ei,点的烤肉数量为
ci,点的烤肉所需烘烤时间为 di,

擒贼先擒王:你该控制谁?

知道了什么样的网络是可控的,那么,如何才能以最高效的方式对网络进行控制呢?根据Yang-Yu
Liu等人在2011年提出的“最小输入定理”,只需要三步。

新浦京www81707con 9最小输入定理步骤。供图:成慧敏
张忠元。

第一步:把原始网络转换成二部图。就是把网络中所有的节点排好后左右各放一列。左边这列是网络图中有箭头出发的节点,用“+”代表;右边这列是网络图中被箭头指向的节点,用“-”代表,两列节点之间是否有连边由原始网络决定,比如原始网络中存在由A出发指向B的连边,那么在二部图“+”列的A与“-”列的B之间就应该有连边。

第二步:根据二部图求最大匹配。什么是匹配呢?在连好边的二部图里,如果一条连边既没有和其他连边共用出发点,也没有和其他连边共用终点,那么这条连边所连接的两个节点就匹配了。最大匹配,就是尽可能多的让左右两列的节点都能匹配在一起。如果我们以丈夫和妻子分别代表左列和右列,一个丈夫节点连到两个妻子节点这种情况不是匹配,反过来一个妻子节点连到两个丈夫节点的情况也不是匹配。因此一夫多妻和一妻多夫都不是匹配,只有一妻一夫才算匹配。而最大匹配就是在一夫一妻的前提下最大限度地减少左右两列中单身节点的数量。

新浦京www81707con 10最大匹配就是在一夫一妻的前提下撮合做多对夫妻。供图:成慧敏
张忠元。

第三步:实现最大匹配后,对右列中没有匹配上的的节点输入控制信号就能控制全网。

回想一下刚才由五个节点组成的可控网络图(c),下面我们以它为原始网络为大家详细介绍最小输入定理。

首先,我们将原始网络结构(下面的图i)转换成二部图,参与到网络中的角色有节点1至节点5,我们把他们列在“+”和“-”两列中。“+”列表示箭头的出发节点,“-”列表示箭头的指向节点,如图(i)所示。

接下来找出该图的最大匹配,先把所有的指向关系间连线,这时“一妻多夫”的情况出现(节点2和节点5同时指向节点4),“一夫多妻”情况也出现了(节点2同时指向节点3和节点2
)。对于该图,存在两种匹配方式:第1种有3个匹配节点(节点1–>节点2、节点2–>节点4、节点4–>节点5);第2种有4个匹配节点(节点1–>节点2、节点2–>节点3、节点4–>节点5、节点5–>节点4)。显然,第2种匹配方式为最大匹配。

确定好最大匹配后,我们为最大匹配的连边标上红色。红色连边即为匹配连接,红色连边对应的右列中的“-”节点为匹配节点,也就是图(ii)和(iii)中的绿色节点;而右列中没有被红色连边相连的“-”
节点就是非匹配节点。匹配节点都处于“可控”的状态。我们可以通过控制左列中与红色连边相连的“+”节点来控制它们。例如节点3受到节点2的管理,节点2受到节点1的管理,而在没有控制源的情况下,节点1则处于“无人管理”的状态。所以我们(控制源)只需要对节点1这个非匹配节点输入控制信号就能实现整个网络的目的了。

新浦京www81707con 11 最小输入定理实例展示。供图:成慧敏
张忠元。

         
每个人要烤的肉可以分成若干份在同时烤,问是否存在一种方案可以满足所有顾客的需求。

别忙出去搞控制!

都看懂了?准备去控制复杂的客户网络和七大姑八大姨的相亲网络了?别忙,你可能盲目乐观了。咱们现在还只是找到了身边的“静香们”。如何控制她们,如何通过她们去控制整个网络,这还需要更深的学问来指导生活。“最小输入定理”虽然在理论上解决了如何以最小的成本控制整个网络的分析,但是,具体输入什么样的控制信号能使得网络达到期望状态?以及,如何将复杂网络可控性的理论应用到现实生活中?这些问题的答案仍然需要通过大量的研究工作来一一作答。这些也是研究复杂网络的科学家们在未来努力的方向。(编辑:明天 婉珺)

题图来源

分析: 将所有的到达时间和结束时间按升序排序,得到 x <= 2n-1
个时间区间。

参考文献:

  1. Liu Y Y, Slotine J J, Barabási A L. Controllability of
    complexnetworks[J]. Nature, 2011, 473(7346): 167-173.
  2. Liu Y Y, Barabási A L. Control principles of complex networks[J].
    arXivpreprint arXiv:1508.05384, 2015.
  3. RATHORE T, PRATHEEK C H S. STUDY ON CONTROLLABILITY OF
    COMPLEXNETWORKS[J].
  4. 侯绿林,老松杨, 肖延东, 等.复杂网络可控性研究现状综述[J]. 物理学报,
    2015 (18): 477-487.

 

          建图:

          s为源,t为汇,

          每个顾客i作为一个结点并连边(s, i, ni*ti)

          每个区间j作为一个结点并连边(j, t, (ej-sj)*M),其中sj,
ej分别表示区间j的起始时间和终止时间

          对任意顾客i和区间j,若 [sj, ej] 完全包含在 [si, ei]
之中,则连边(i, j, INF)

          若最大流等于 ∑ni*ti 则是 Yes,否则是 No。

这题我是觉得不科学的,比如一组数据:

1 10

1 2 3 5

顾客要的东西要五分钟烤完,然后你特么的让人家等了2分钟就好了,你是怎么做到的呀O__O
“…

当然,如果真的要较真的话这题我就不会做了(捂脸)

代码:

新浦京www81707con 12新浦京www81707con 13

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 370000
  8 #define MAXP 606
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Cust
 17 {
 18     int start,last,stay;
 19 }cust[MAXP];
 20 int head[MAXP];
 21 int time[MAXP*2];
 22 int stay[MAXP];
 23 int cur[MAXP];
 24 int pre[MAXP];
 25 int stack[MAXE];
 26 int used[MAXP];
 27 int ent;
 28 int n,m,s,t;
 29 int num;
 30 void add(int start,int last,int f)
 31 {
 32     edge[ent].s=start;
 33     edge[ent].t=last;
 34     edge[ent].f=f;
 35     edge[ent].next=head[start];
 36     head[start]=ent++;
 37     edge[ent].s=last;
 38     edge[ent].t=start;
 39     edge[ent].f=0;
 40     edge[ent].next=head[last];
 41     head[last]=ent++;
 42 }
 43 bool bfs(int S,int T)
 44 {
 45     memset(pre,-1,sizeof(pre));
 46     pre[S]=0;
 47     queue<int>q;
 48     q.push(S);
 49     while(!q.empty())
 50     {
 51         int temp=q.front();
 52         q.pop();
 53         for(int i=head[temp]; i!=-1; i=edge[i].next)
 54         {
 55             int temp2=edge[i].t;
 56             if(pre[temp2]==-1&&edge[i].f)
 57             {
 58                 pre[temp2]=pre[temp]+1;
 59                 q.push(temp2);
 60             }
 61         }
 62     }
 63     return pre[T]!=-1;
 64 }
 65 int dinic(int start,int last)
 66 {
 67     int flow=0,now;
 68     while(bfs(start,last))
 69     {
 70         int top=0;
 71         memcpy(cur,head,sizeof(head));
 72         int u=start;
 73         while(1)
 74         {
 75             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 76             {
 77                 int minn=INT_MAX;
 78                 for(int i=0; i<top; i++)
 79                 {
 80                     if(minn>edge[stack[i]].f)
 81                     {
 82                         minn=edge[stack[i]].f;
 83                         now=i;
 84                     }
 85                 }
 86                 for(int i=0;i<top;i++)
 87                 {
 88                     edge[stack[i]].f-=minn;
 89                     edge[stack[i]^1].f+=minn;
 90                 }
 91                 flow+=minn;
 92                 top=now;
 93                 u=edge[stack[top]].s;
 94             }
 95             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 96                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 97                     break;
 98             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 99             {
100                 if(top==0)break;
101                 pre[u]=-1;
102                 u=edge[stack[--top]].s;
103             }
104             else//如果找到了继续运行
105             {
106                 stack[top++]=cur[u];
107                 u=edge[cur[u]].t;
108             }
109         }
110     }
111     return flow;
112 }
113 int main()
114 {
115     while(~scanf("%d%d",&n,&m))
116     {
117         int si,ni,ti;
118         int sum=0;
119         memset(head,-1,sizeof(head));
120         ent=0;
121         s=0;t=3*n+1;
122         int tot=0;
123         for(int i=1;i<=n;i++)
124         {
125             scanf("%d%d%d%d",&cust[i].start,&ni,&cust[i].last,&ti);
126             cust[i].stay=ni*ti;
127             sum+=cust[i].stay;
128             time[tot++]=cust[i].start;
129             time[tot++]=cust[i].last;
130         }
131         sort(time,time+2*n);
132         for(int i=1;i<=n;i++)
133             add(s,i,cust[i].stay);//cout<<"road:"<<i<<" start:"<<cust[i].start<<" last:"<<cust[i].last<<endl;}
134         //cout<<"time[0]:"<<time[0]<<endl;
135         for(int i=1;i<2*n;i++)
136         {
137             //cout<<"time["<<i<<"]:"<<time[i]<<endl;
138             if(time[i]==time[i-1])continue;
139             for(int j=1;j<=n;j++)
140             {
141                 if(cust[j].start<=time[i-1]&&cust[j].last>=time[i])
142                     add(j,n+i,m*(time[i]-time[i-1]));
143             }
144             add(n+i,t,m*(time[i]-time[i-1]));
145         }
146         //for(int i=0;i<ent;i++)
147             //if(edge[i].f)cout<<"s:"<<edge[i].s<<" t:"<<edge[i].t<<" f:"<<edge[i].f<<endl;
148         if(sum==dinic(s,t))
149             printf("Yes\n");
150         else printf("No\n");
151     }
152     return 0;
153 }

View Code

2.poj3469

题意:一台双核电脑,给你多个任务,分别给出每个任务在第一个核和第二个核上运行的消耗。后面的m行输入是给出两个任务在两个不同核上运行需要付出的额外消耗。

建图:把每个任务作为节点,在超级源点与任务间的连一条边,其容量为给任务在核1上运行的消耗,在该任务节点与超级汇点之间连一条边,容量为该任务在核2上运行的消耗。

          
在任务之间连接无向边,容量为两个任务不在同一核上运行的额外消耗。

这题巧就巧在这句:在任务之间连接无向边,容量为两个任务不在同一核上运行的额外消耗。表示不是很理解,如果有大神在跪求带我装逼带我飞n(*≧▽≦*)n

代码:

新浦京www81707con 14新浦京www81707con 15

  1 #include<iostream>
  2 #include<queue>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<climits>
  6 #define MAXE 1641000
  7 #define MAXP 20010
  8 #define Max(a,b) a>b?a:b
  9 #define Min(a,b) a<b?a:b
 10 using namespace std;
 11 struct Edge
 12 {
 13     int s,t,f,next;
 14 } edge[MAXE];
 15 int head[MAXP];
 16 int cur[MAXP];
 17 int pre[MAXP];
 18 int stack[MAXE];
 19 int used[MAXP];
 20 int ent;
 21 int n,m,s,t;
 22 int num;
 23 void add(int start,int last,int f)
 24 {
 25     edge[ent].s=start;
 26     edge[ent].t=last;
 27     edge[ent].f=f;
 28     edge[ent].next=head[start];
 29     head[start]=ent++;
 30     edge[ent].s=last;
 31     edge[ent].t=start;
 32     edge[ent].f=0;
 33     edge[ent].next=head[last];
 34     head[last]=ent++;
 35 }
 36 bool bfs(int S,int T)
 37 {
 38     memset(pre,-1,sizeof(pre));
 39     pre[S]=0;
 40     queue<int>q;
 41     q.push(S);
 42     while(!q.empty())
 43     {
 44         int temp=q.front();
 45         q.pop();
 46         for(int i=head[temp]; i!=-1; i=edge[i].next)
 47         {
 48             int temp2=edge[i].t;
 49             if(pre[temp2]==-1&&edge[i].f)
 50             {
 51                 pre[temp2]=pre[temp]+1;
 52                 q.push(temp2);
 53             }
 54         }
 55     }
 56     return pre[T]!=-1;
 57 }
 58 int dinic(int start,int last)
 59 {
 60     int flow=0,now;
 61     while(bfs(start,last))
 62     {
 63         int top=0;
 64         memcpy(cur,head,sizeof(head));
 65         int u=start;
 66         while(1)
 67         {
 68             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 69             {
 70                 int minn=INT_MAX;
 71                 for(int i=0; i<top; i++)
 72                 {
 73                     if(minn>edge[stack[i]].f)
 74                     {
 75                         minn=edge[stack[i]].f;
 76                         now=i;
 77                     }
 78                 }
 79                 for(int i=0;i<top;i++)
 80                 {
 81                     edge[stack[i]].f-=minn;
 82                     edge[stack[i]^1].f+=minn;
 83                 }
 84                 flow+=minn;
 85                 top=now;
 86                 u=edge[stack[top]].s;
 87             }
 88             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 89                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 90                     break;
 91             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 92             {
 93                 if(top==0)break;
 94                 pre[u]=-1;
 95                 u=edge[stack[--top]].s;
 96             }
 97             else//如果找到了继续运行
 98             {
 99                 stack[top++]=cur[u];
100                 u=edge[cur[u]].t;
101             }
102         }
103     }
104     return flow;
105 }
106 int main()
107 {
108     while(~scanf("%d%d",&n,&m))
109     {
110         memset(head,-1,sizeof(head));
111         ent=0;
112         s=0;t=n+1;
113         int cost1,cost2;
114         for(int i=1;i<=n;i++)
115         {
116             scanf("%d%d",&cost1,&cost2);
117             add(s,i,cost1);
118             add(i,t,cost2);
119         }
120         int u,v,cost;
121         for(int i=1;i<=m;i++)
122         {
123             scanf("%d%d%d",&u,&v,&cost);
124             add(u,v,cost);
125             add(v,u,cost);
126         }
127         printf("%d\n",dinic(s,t));
128     }
129     return 0;
130 }

View Code

 3.hdu3061

中文题,思路就是最大权闭合图(妈蛋我竟然一直没看出来,没活路了,不管什么算法不刷题果然都特么不行呀/(ㄒoㄒ)/~~)

附带一点本人对最大权闭合图的理解:如果连边2->3流量为无穷,代表的不是2牵制3,而是3牵制2,即必须完成了3才能去完成2,而不是完成了2才能去完成3

代码:

新浦京www81707con 16新浦京www81707con 17

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 250000
  8 #define MAXP 500
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Cust
 17 {
 18     int start,last,stay;
 19 }cust[MAXP];
 20 int head[MAXP];
 21 int time[MAXP*2];
 22 int stay[MAXP];
 23 int cur[MAXP];
 24 int pre[MAXP];
 25 int stack[MAXE];
 26 int used[MAXP];
 27 int ent;
 28 int n,m,s,t;
 29 int num;
 30 void add(int start,int last,int f)
 31 {
 32     edge[ent].s=start;
 33     edge[ent].t=last;
 34     edge[ent].f=f;
 35     edge[ent].next=head[start];
 36     head[start]=ent++;
 37     edge[ent].s=last;
 38     edge[ent].t=start;
 39     edge[ent].f=0;
 40     edge[ent].next=head[last];
 41     head[last]=ent++;
 42 }
 43 bool bfs(int S,int T)
 44 {
 45     memset(pre,-1,sizeof(pre));
 46     pre[S]=0;
 47     queue<int>q;
 48     q.push(S);
 49     while(!q.empty())
 50     {
 51         int temp=q.front();
 52         q.pop();
 53         for(int i=head[temp]; i!=-1; i=edge[i].next)
 54         {
 55             int temp2=edge[i].t;
 56             if(pre[temp2]==-1&&edge[i].f)
 57             {
 58                 pre[temp2]=pre[temp]+1;
 59                 q.push(temp2);
 60             }
 61         }
 62     }
 63     return pre[T]!=-1;
 64 }
 65 int dinic(int start,int last)
 66 {
 67     int flow=0,now;
 68     while(bfs(start,last))
 69     {
 70         int top=0;
 71         memcpy(cur,head,sizeof(head));
 72         int u=start;
 73         while(1)
 74         {
 75             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 76             {
 77                 int minn=INT_MAX;
 78                 for(int i=0; i<top; i++)
 79                 {
 80                     if(minn>edge[stack[i]].f)
 81                     {
 82                         minn=edge[stack[i]].f;
 83                         now=i;
 84                     }
 85                 }
 86                 for(int i=0;i<top;i++)
 87                 {
 88                     edge[stack[i]].f-=minn;
 89                     edge[stack[i]^1].f+=minn;
 90                 }
 91                 flow+=minn;
 92                 top=now;
 93                 u=edge[stack[top]].s;
 94             }
 95             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 96                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 97                     break;
 98             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 99             {
100                 if(top==0)break;
101                 pre[u]=-1;
102                 u=edge[stack[--top]].s;
103             }
104             else//如果找到了继续运行
105             {
106                 stack[top++]=cur[u];
107                 u=edge[cur[u]].t;
108             }
109         }
110     }
111     return flow;
112 }
113 int main()
114 {
115     while(~scanf("%d%d",&n,&m))
116     {
117         memset(head,-1,sizeof(head));
118         ent=0;s=0;t=n+1;
119         int cost,sum=0;
120         for(int i=1;i<=n;i++)
121         {
122             scanf("%d",&cost);
123             if(cost>0)
124             {
125                 add(s,i,cost);
126                 sum+=cost;
127             }
128             else
129                 add(i,t,-cost);
130         }
131         for(int i=1;i<=m;i++)
132         {
133             int u,v;
134             scanf("%d%d",&u,&v);
135             add(u,v,INT_MAX);
136         }
137         printf("%d\n",sum-dinic(s,t));
138     }
139     return 0;
140 }

View Code

 

4.hdu1733&&poj3057

hdu1733题意:

有一个类似于迷宫搜索的图,‘.’代表的是无人的路,’X’代表有人的点,’#’代表此点不可通过,’@’代表门口。每个位置每一秒钟只能站一个人,每个位置到上下左右点的时间为1,问你所有人能不能出去,能出去输出所有人都出去的最小时间,否则输出-1.

建图:

1.拆点,对于第d天,每个点已被拆为d+1个点,下标代号成等差数列 公差n*m.

2.起始的时候,s向第0天的n*m中是人的点连条权值为1的边。

3.而后从小到大枚举每天,假设第t天,那么对于t-1天的点可以向四周扩展,或不动,向对应在第t天新加的点连条权为1的边,然后对第t天的n*m点,如果是出口则向汇点连条权值为1的边,然后从源点到汇点做网络流,如果ans等于人数,则break,return
t。

4.对于没有解的情况,先dfs判断是否有解处理的。

ps:我提一个注意事项,虽然一般没傻逼到一定程度不会出现这种问题/(ㄒoㄒ)/,那就是:i,j对应的位置是(i-1)*m+j而不是(i-1)*n+j,因为这个我wa了20次,花了两天/(ㄒoㄒ)/

代码:

新浦京www81707con 18新浦京www81707con 19

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 2000000
  8 #define MAXP 200024
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Point
 17 {
 18     int x,y;
 19 };
 20 int head[MAXP];
 21 int cur[MAXP];
 22 int pre[MAXP];
 23 int stack[MAXE];
 24 int ent;
 25 int n,m,s,t;
 26 int num;
 27 char map[18][18];
 28 bool can[18][18];
 29 bool visit[18][18];
 30 int dx[5]= {0,0,1,-1,0};
 31 int dy[5]= {1,-1,0,0,0};
 32 bool IN(int x,int y)
 33 {
 34     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='#'&&!visit[x][y];
 35 }
 36 bool BFS(int x,int y)
 37 {
 38     memset(visit,false,sizeof(visit));
 39     Point temp,temp1;
 40     temp.x=x;
 41     temp.y=y;
 42     queue<Point>q;
 43     q.push(temp);
 44     while(!q.empty())
 45     {
 46         temp=q.front();
 47         q.pop();
 48         for(int i=0; i<4; i++)
 49         {
 50             temp1.x=temp.x+dx[i];
 51             temp1.y=temp.y+dy[i];
 52             if(can[temp1.x][temp1.y]||map[temp1.x][temp1.y]=='@')
 53             {
 54                 can[x][y]=can[temp1.x][temp1.y]=true;
 55                 return true;
 56             }
 57             if(IN(temp1.x,temp1.y))
 58             {
 59                 q.push(temp1);
 60                 visit[temp1.x][temp.y]=true;
 61             }
 62         }
 63     }
 64     return false;
 65 }
 66 void add(int start,int last,int f)
 67 {
 68     edge[ent].s=start;
 69     edge[ent].t=last;
 70     edge[ent].f=f;
 71     edge[ent].next=head[start];
 72     head[start]=ent++;
 73     edge[ent].s=last;
 74     edge[ent].t=start;
 75     edge[ent].f=0;
 76     edge[ent].next=head[last];
 77     head[last]=ent++;
 78 }
 79 bool bfs(int S,int T)
 80 {
 81     memset(pre,-1,sizeof(pre));
 82     pre[S]=0;
 83     queue<int>q;
 84     q.push(S);
 85     while(!q.empty())
 86     {
 87         int temp=q.front();
 88         q.pop();
 89         for(int i=head[temp]; i!=-1; i=edge[i].next)
 90         {
 91             int temp2=edge[i].t;
 92             if(pre[temp2]==-1&&edge[i].f)
 93             {
 94                 pre[temp2]=pre[temp]+1;
 95                 q.push(temp2);
 96             }
 97         }
 98     }
 99     return pre[T]!=-1;
100 }
101 int dinic(int start,int last)
102 {
103     int flow=0,now;
104     while(bfs(start,last))
105     {
106         int top=0;
107         memcpy(cur,head,sizeof(head));
108         int u=start;
109         while(1)
110         {
111             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
112             {
113                 int minn=INT_MAX;
114                 for(int i=0; i<top; i++)
115                 {
116                     if(minn>edge[stack[i]].f)
117                     {
118                         minn=edge[stack[i]].f;
119                         now=i;
120                     }
121                 }
122                 for(int i=0; i<top; i++)
123                 {
124                     edge[stack[i]].f-=minn;
125                     edge[stack[i]^1].f+=minn;
126                 }
127                 flow+=minn;
128                 top=now;
129                 u=edge[stack[top]].s;
130             }
131             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
132                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
133                     break;
134             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
135             {
136                 if(top==0)break;
137                 pre[u]=-1;
138                 u=edge[stack[--top]].s;
139             }
140             else//如果找到了继续运行
141             {
142                 stack[top++]=cur[u];
143                 u=edge[cur[u]].t;
144             }
145         }
146     }
147     return flow;
148 }
149 bool in(int x,int y)
150 {
151     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='#';
152 }
153 int main()
154 {
155     while(~scanf("%d%d",&n,&m))
156     {
157         num=0;
158         memset(can,false,sizeof(can));
159         for(int i=1;i<=n;i++)
160         {
161             scanf("%s",map[i]+1);
162         }
163         bool ok=true;
164         for(int i=1; i<=n; i++)
165         {
166             for(int j=1; j<=m; j++)
167             {
168                 if(map[i][j]=='X')
169                 {
170                     num++;
171                     if(!BFS(i,j))
172                     {
173                         ok=false;
174                     }
175                 }
176             }
177         }
178         if(num==0)
179         {
180             cout<<0<<endl;
181             continue;
182         }
183         if(!ok)
184         {
185             printf("-1\n");
186         }
187         else
188         {
189             ent=0;
190             memset(head,-1,sizeof(head));
191             s=0;t=200023;
192             for(int mid=1;; mid++)
193             {
194                 int time=mid;
195                 for(int i=1; i<=n; i++)
196                 {
197                     for(int j=1; j<=m; j++)
198                     {
199                         if(map[i][j]=='#')continue;
200                         if(map[i][j]=='@')
201                         {
202                             add(time*2*n*m+(i-1)*m+j,t,1);
203                             continue;
204                         }
205                         add((time-1)*2*m*n+(i-1)*m+j,(time*2-1)*n*m+(i-1)*m+j,1);
206                         if(time==1&&map[i][j]=='X')
207                             add(s,(i-1)*m+j,1);
208                         for(int k=0; k<5; k++)
209                         {
210                             int x=i+dx[k];
211                             int y=j+dy[k];
212                             if(in(x,y))
213                             {
214                                 add((time*2-1)*n*m+(i-1)*m+j,time*2*n*m+(x-1)*m+y,1);
215                             }
216                         }
217                     }
218                 }
219                 int temp=dinic(s,t);
220                 if(temp==num)
221                 {
222                     cout<<mid<<endl;
223                     break;
224                 }
225                 num-=temp;
226             }
227         }
228     }
229     return 0;
230 }

View Code

poj3057:

基本一样,两个不同:1.开始时每个空格位置都有一个人,2:后来除了门之外别的地方都可以有很多人,但是出去的话一次只能出去一个人。

代码:

新浦京www81707con 20新浦京www81707con 21

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 1000000
  8 #define MAXP 20000
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Point
 17 {
 18     int x,y;
 19 };
 20 int head[MAXP];
 21 int cur[MAXP];
 22 int pre[MAXP];
 23 int stack[MAXE];
 24 int ent;
 25 int n,m,s,t;
 26 int num;
 27 char map[14][14];
 28 bool can[14][14];
 29 bool visit[14][14];
 30 int dx[5]= {0,0,1,-1,0};
 31 int dy[5]= {1,-1,0,0,0};
 32 bool IN(int x,int y)
 33 {
 34     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='X'&&!visit[x][y];
 35 }
 36 bool BFS(int x,int y)
 37 {
 38     memset(visit,false,sizeof(visit));
 39     Point temp,temp1;
 40     temp.x=x;
 41     temp.y=y;
 42     visit[x][y]=true;
 43     queue<Point>q;
 44     q.push(temp);
 45     while(!q.empty())
 46     {
 47         temp=q.front();
 48         q.pop();
 49         for(int i=0; i<4; i++)
 50         {
 51             temp1.x=temp.x+dx[i];
 52             temp1.y=temp.y+dy[i];
 53             if(can[temp1.x][temp1.y]||map[temp1.x][temp1.y]=='D')
 54             {
 55                 can[x][y]=can[temp1.x][temp1.y]=true;
 56                 return true;
 57             }
 58             if(IN(temp1.x,temp1.y))
 59             {
 60                 q.push(temp1);
 61                 visit[temp1.x][temp.y]=true;
 62             }
 63         }
 64     }
 65     return false;
 66 }
 67 void add(int start,int last,int f)
 68 {
 69     edge[ent].s=start;
 70     edge[ent].t=last;
 71     edge[ent].f=f;
 72     edge[ent].next=head[start];
 73     head[start]=ent++;
 74     edge[ent].s=last;
 75     edge[ent].t=start;
 76     edge[ent].f=0;
 77     edge[ent].next=head[last];
 78     head[last]=ent++;
 79 }
 80 bool bfs(int S,int T)
 81 {
 82     memset(pre,-1,sizeof(pre));
 83     pre[S]=0;
 84     queue<int>q;
 85     q.push(S);
 86     while(!q.empty())
 87     {
 88         int temp=q.front();
 89         q.pop();
 90         for(int i=head[temp]; i!=-1; i=edge[i].next)
 91         {
 92             int temp2=edge[i].t;
 93             if(pre[temp2]==-1&&edge[i].f)
 94             {
 95                 pre[temp2]=pre[temp]+1;
 96                 q.push(temp2);
 97             }
 98         }
 99     }
100     return pre[T]!=-1;
101 }
102 int dinic(int start,int last)
103 {
104     int flow=0,now;
105     while(bfs(start,last))
106     {
107         int top=0;
108         memcpy(cur,head,sizeof(head));
109         int u=start;
110         while(1)
111         {
112             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
113             {
114                 int minn=INT_MAX;
115                 for(int i=0; i<top; i++)
116                 {
117                     if(minn>edge[stack[i]].f)
118                     {
119                         minn=edge[stack[i]].f;
120                         now=i;
121                     }
122                 }
123                 for(int i=0; i<top; i++)
124                 {
125                     edge[stack[i]].f-=minn;
126                     edge[stack[i]^1].f+=minn;
127                 }
128                 flow+=minn;
129                 top=now;
130                 u=edge[stack[top]].s;
131             }
132             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
133                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
134                     break;
135             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
136             {
137                 if(top==0)break;
138                 pre[u]=-1;
139                 u=edge[stack[--top]].s;
140             }
141             else//如果找到了继续运行
142             {
143                 stack[top++]=cur[u];
144                 u=edge[cur[u]].t;
145             }
146         }
147     }
148     return flow;
149 }
150 bool in(int x,int y)
151 {
152     return x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='X';
153 }
154 int main()
155 {
156     int cas;
157     cin>>cas;
158     while(cas--)
159     {
160         scanf("%d%d",&n,&m);
161         num=0;
162         memset(can,false,sizeof(can));
163         for(int i=1; i<=n; i++)
164             scanf("%s",map[i]+1);
165         bool ok=true;
166         for(int i=1; i<=n; i++)
167         {
168             for(int j=1; j<=m; j++)
169             {
170                 if(map[i][j]=='.')
171                 {
172                     num++;
173                     if(!BFS(i,j))
174                     {
175                         ok=false;
176                     }
177                 }
178                 /*if(map[i][j]=='D')
179                 {
180                     int oks=0;
181                     for(int k=0;k<4;k++)
182                     {
183                         int x=i+dx[k];
184                         int y=j+dy[k];
185                         if(x<1||x>n||y<1||y>m)continue;
186                         if(map[x][y]=='.')
187                             oks++;
188                     }
189                     if(!oks)
190                         map[i][j]='X';
191                 }*/
192             }
193         }
194         if(num==0)
195         {
196             cout<<0<<endl;
197             continue;
198         }
199         if(!ok)
200         {
201             printf("impossible\n");
202         }
203         else
204         {
205             memset(head,-1,sizeof(head));
206             ent=0;
207             s=0;
208             t=19999;
209             for(int mid=1;; mid++)
210             {
211                 //s=0;
212                 //t=(mid+1)*n*m+1;
213                 int time=mid;
214                 for(int i=1; i<=n; i++)
215                 {
216                     for(int j=1; j<=m; j++)
217                     {
218                         if(map[i][j]=='X')continue;
219                         if(time==1&&map[i][j]=='.')
220                             add(s,(i-1)*m+j,1);
221                         if(map[i][j]=='D')
222                         {
223                             add(time*n*m+(i-1)*m+j,t,1);
224                             continue;
225                         }
226                         for(int k=0; k<5; k++)
227                         {
228                             int x=i+dx[k];
229                             int y=j+dy[k];
230                             if(in(x,y))
231                             {
232                                 add((time-1)*n*m+(i-1)*m+j,time*n*m+(x-1)*m+y,INT_MAX);
233                             }
234                         }
235                     }
236                 }
237                 int temp=dinic(s,t);
238                 if(temp==num)
239                 {
240                     cout<<mid<<endl;
241                     break;
242                 }
243                 num-=temp;
244             }
245         }
246     }
247     return 0;
248 }

View Code

 

 

5.poj2396  有上下界有源汇的可行流

题意:

题目大意:有一个n*m的矩阵,每个位置(i,j)都有一个值,接下来输入n个数,每个数代表矩阵对应行的和,接下来输入m个数,每个数代表对应列的和。接下来有Q个操作,每个操作输入i
j c val。

1、当c为’>’: 表示第i行j列的数值要大于val。(实际下级要设为val+1)

2、当c为'<‘: 表示第i行j列的数值要小于val。(实际上界要设为val-1)

3、当c为’=’: 表示第i行j列的数值要等于val。

让你求是否存在满足要求的矩阵,有则输出对应的矩阵,无则输出”impossible”。

注意:i=0||j=0表示那一行||那一列的每一个数都符合要求而不是所有数的和符合要求,妈的被坑了一天有木有,直接哭晕在厕所,真的抓狂了,英语差简直没活路呀

解题思路:

增设一源点s和一汇点d,源点s和每行的代表虚拟节点row[i]相连,权值为该行的权值总和,每列的代表虚拟节点和汇点d相连,权值为该列的权值总和,行连接列代表节点(i,j)即i行j列,它的容量上下界根据题目来确定。

           
连接一条附加边(d,s)容量为无穷,剩下的操作和无源汇有上下界的可行流一样。

注意:上下界不能出来一个就加一次这样会出错的,一定要把所有的操作全部搞定然后在确定最终的上下界,不然也是会wa的

代码:

新浦京www81707con 22新浦京www81707con 23

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 5000000
  8 #define MAXP 4400
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 int head[MAXP];
 17 int flow[MAXP];
 18 int degree[MAXP];
 19 int cur[MAXP];
 20 int pre[MAXP];
 21 int stack[MAXE];
 22 int maxn[MAXP];
 23 int minn[MAXP];
 24 int ent;
 25 int n,m,s,t,supers,supert;
 26 int num;
 27 void add(int start,int last,int f)
 28 {
 29     edge[ent].s=start;
 30     edge[ent].t=last;
 31     edge[ent].f=f;
 32     edge[ent].next=head[start];
 33     head[start]=ent++;
 34     edge[ent].s=last;
 35     edge[ent].t=start;
 36     edge[ent].f=0;
 37     edge[ent].next=head[last];
 38     head[last]=ent++;
 39 }
 40 bool bfs(int S,int T)
 41 {
 42     memset(pre,-1,sizeof(pre));
 43     pre[S]=0;
 44     queue<int>q;
 45     q.push(S);
 46     while(!q.empty())
 47     {
 48         int temp=q.front();
 49         q.pop();
 50         for(int i=head[temp]; i!=-1; i=edge[i].next)
 51         {
 52             int temp2=edge[i].t;
 53             if(pre[temp2]==-1&&edge[i].f)
 54             {
 55                 pre[temp2]=pre[temp]+1;
 56                 q.push(temp2);
 57             }
 58         }
 59     }
 60     return pre[T]!=-1;
 61 }
 62 int dinic(int start,int last)
 63 {
 64     int flow=0,now;
 65     while(bfs(start,last))
 66     {
 67         int top=0;
 68         memcpy(cur,head,sizeof(head));
 69         int u=start;
 70         while(1)
 71         {
 72             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 73             {
 74                 int minn=INT_MAX;
 75                 for(int i=0; i<top; i++)
 76                 {
 77                     if(minn>edge[stack[i]].f)
 78                     {
 79                         minn=edge[stack[i]].f;
 80                         now=i;
 81                     }
 82                 }
 83                 for(int i=0; i<top; i++)
 84                 {
 85                     edge[stack[i]].f-=minn;
 86                     edge[stack[i]^1].f+=minn;
 87                 }
 88                 flow+=minn;
 89                 top=now;
 90                 u=edge[stack[top]].s;
 91             }
 92             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 93                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 94                     break;
 95             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 96             {
 97                 if(top==0)break;
 98                 pre[u]=-1;
 99                 u=edge[stack[--top]].s;
100             }
101             else//如果找到了继续运行
102             {
103                 stack[top++]=cur[u];
104                 u=edge[cur[u]].t;
105             }
106         }
107     }
108     return flow;
109 }
110 int main()
111 {
112     int cas;
113     cin>>cas;
114     while(cas--)
115     {
116         scanf("%d%d",&n,&m);
117         memset(head,-1,sizeof(head));
118         memset(flow,0,sizeof(flow));
119         memset(maxn,-1,sizeof(maxn));
120         memset(minn,0,sizeof(minn));
121         ent=0;
122         int ok=1;
123         s=0;
124         t=n+m+n*m+1;
125         supers=t+1;
126         supert=t+2;
127         int hang[200+1];
128         int lie[200+1];
129         int sumhang=0,sumlie=0;
130         memset(degree,0,sizeof(degree));
131         int temp;
132         for(int i=1; i<=n; i++)
133         {
134             scanf("%d",&temp);
135             if(temp<0)ok=0;
136             hang[i]=temp;
137             sumhang+=temp;
138             degree[i]+=temp;
139             degree[s]-=temp;
140             add(s,i,0);
141         }
142         for(int i=n+1; i<=n+m; i++)
143         {
144             scanf("%d",&temp);
145             if(temp<0)ok=0;
146             lie[i-n]=temp;
147             sumlie+=temp;
148             degree[i]-=temp;
149             degree[t]+=temp;
150             add(i,t,0);
151         }
152         add(t,s,INT_MAX);
153         if(sumhang!=sumlie)ok=0;
154         scanf("%d",&num);
155         int u,v,sum;
156         char chara;
157         for(int i=1; i<=num; i++)
158         {
159             cin>>u>>v>>chara>>sum;
160             int s1=u,t1=u;
161             int s2=v,t2=v;
162             if(u==0)s1=1,t1=n;
163             if(v==0)s2=1,t2=m;
164             for(u=s1;u<=t1;u++)
165             for(v=s2;v<=t2;v++)
166             {
167                 if(chara=='<')
168                 {
169                     if(sum<=0)
170                         ok=0;
171                     else
172                     {
173                         if(maxn[(u-1)*m+v]==-1)
174                             maxn[(u-1)*m+v]=sum-1;
175                         else maxn[(u-1)*m+v]=Min(maxn[(u-1)*m+v],sum-1);
176                     }
177                 }
178                 else if(chara=='=')
179                 {
180                     if(sum<0)ok=0;
181                     if(maxn[(u-1)*m+v]!=-1&&maxn[(u-1)*m+v]<sum)ok=0;
182                     if(minn[(u-1)*m+v]>sum)ok=0;
183                     maxn[(u-1)*m+v]=sum;
184                     minn[(u-1)*m+v]=sum;
185                 }
186                 else if(chara=='>')
187                 {
188                     if(sum<0)continue;
189                     if(sum>=hang[u])
190                         ok=0;
191                     else
192                     {
193                         minn[(u-1)*m+v]=Max(minn[(u-1)*m+v],sum+1);
194                     }
195                 }
196             }
197         }
198         for(int i=1; i<=n; i++)
199         {
200             if(!ok)break;
201             for(int j=1; j<=m; j++)
202             {
203                 if(maxn[(i-1)*m+j]==-1)maxn[(i-1)*m+j]=hang[i];
204                 if(maxn[(i-1)*m+j]<minn[(i-1)*m+j])
205                 {
206                     ok=0;
207                     break;
208                 }
209                 degree[i]-=minn[(i-1)*m+j];
210                 degree[j+n]+=minn[(i-1)*m+j];
211                 add(i,(i-1)*m+j+n+m,maxn[(i-1)*m+j]-minn[(i-1)*m+j]);
212                 add((i-1)*m+j+n+m,j+n,maxn[(i-1)*m+j]-minn[(i-1)*m+j]);
213                 flow[(i-1)*m+j]=minn[(i-1)*m+j];
214             }
215         }
216         if(!ok)
217         {
218             printf("IMPOSSIBLE\n");
219             if(cas)cout<<endl;
220             continue;
221         }
222         int all=0;
223         add(t,s,INT_MAX);
224         for(int i=s; i<=t; i++)
225         {
226             if(degree[i]<0)
227                 add(i,supert,-degree[i]);
228             else if(degree[i]>0)
229             {
230                 add(supers,i,degree[i]);
231                 all+=degree[i];
232             }
233         }
234         if(all==dinic(supers,supert))
235         {
236             for(int j=1; j<=n; j++)
237             {
238                 for(int i=head[j]; i!=-1; i=edge[i].next)
239                 {
240                     int aim=edge[i].t-n-m;
241                     if(aim>0&&aim<=n*m)
242                     {
243                         flow[aim]+=edge[i^1].f;
244                     }
245                 }
246             }
247             for(int i=1; i<=n; i++)
248             {
249                 for(int j=1; j<m; j++)
250                 {
251                     cout<<flow[(i-1)*m+j]<<" ";
252                 }
253                 cout<<flow[i*m]<<endl;
254             }
255         }
256         else cout<<"IMPOSSIBLE"<<endl;
257         if(cas)cout<<endl;
258     }
259     return 0;
260 }

View Code

 

hust1024
分层网络流(虽然这不是我做的第一道二分枚举可行流的题目,但是对于自己能30分钟之内独立的不看题解a掉他还是很激动的,当然必然用了最大流模板2333333333)

题意:

有n男n女,有m对男女喜欢对方,每个男的或者女的最多和k个他不喜欢的女的或男的跳舞,然后是输入m对喜欢对方的男女,然后叫你求出最多你给这么多人配几次对,每次配对都不能给一个人陪曾经给它配过的人。

思路:

网络流,关键在于建图。

             
 把男性拆成两个点,分别放置在两个集合内,Xa和Xb,女性拆成两个点,分别放置在Ya和Yb内。Xa到Xb连接一条有向边,权值为k,Yb到Ya连接一条有向边,权值为k。当boy喜欢girl时,Xa和Ya之间连接一条对应的有向边权值为1,当boy不喜欢girl时,Xb和Yb连接一条对应的有向边,权值为1。

             最后二分枚举可行解ans,
超级源点到Xa的每个点连接一条有向边,权值为ans,Ya内的每个点和超级汇点连接一条有向边,权值也为ans。最后流啊流,最大流满足max_flow==n*ans时,继续二分,直到找到最优解。(这应该会比较快,不过本人是从小到大枚举的)

代码:

新浦京www81707con 24新浦京www81707con 25

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 500000
  8 #define MAXP 450
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 int head[MAXP];
 17 int cur[MAXP];
 18 int pre[MAXP];
 19 int stack[MAXE];
 20 int ent;
 21 int n,m,k,s,t;
 22 int num;
 23 int dx[4]={0,0,1,-1};
 24 int dy[4]={1,-1,0,0};
 25 bool in(int x,int y)
 26 {
 27     return x>=1&&x<=n&&y>=1&&y<=m;
 28 }
 29 void add(int start,int last,int f)
 30 {
 31     edge[ent].s=start;
 32     edge[ent].t=last;
 33     edge[ent].f=f;
 34     edge[ent].next=head[start];
 35     head[start]=ent++;
 36     edge[ent].s=last;
 37     edge[ent].t=start;
 38     edge[ent].f=0;
 39     edge[ent].next=head[last];
 40     head[last]=ent++;
 41 }
 42 bool bfs(int S,int T)
 43 {
 44     memset(pre,-1,sizeof(pre));
 45     pre[S]=0;
 46     queue<int>q;
 47     q.push(S);
 48     while(!q.empty())
 49     {
 50         int temp=q.front();
 51         q.pop();
 52         for(int i=head[temp]; i!=-1; i=edge[i].next)
 53         {
 54             int temp2=edge[i].t;
 55             if(pre[temp2]==-1&&edge[i].f)
 56             {
 57                 pre[temp2]=pre[temp]+1;
 58                 q.push(temp2);
 59             }
 60         }
 61     }
 62     return pre[T]!=-1;
 63 }
 64 int dinic(int start,int last)
 65 {
 66     int flow=0,now;
 67     while(bfs(start,last))
 68     {
 69         int top=0;
 70         memcpy(cur,head,sizeof(head));
 71         int u=start;
 72         while(1)
 73         {
 74             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 75             {
 76                 int minn=INT_MAX;
 77                 for(int i=0; i<top; i++)
 78                 {
 79                     if(minn>edge[stack[i]].f)
 80                     {
 81                         minn=edge[stack[i]].f;
 82                         now=i;
 83                     }
 84                 }
 85                 for(int i=0; i<top; i++)
 86                 {
 87                     edge[stack[i]].f-=minn;
 88                     edge[stack[i]^1].f+=minn;
 89                 }
 90                 flow+=minn;
 91                 top=now;
 92                 u=edge[stack[top]].s;
 93             }
 94             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
 95                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
 96                     break;
 97             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
 98             {
 99                 if(top==0)break;
100                 pre[u]=-1;
101                 u=edge[stack[--top]].s;
102             }
103             else//如果找到了继续运行
104             {
105                 stack[top++]=cur[u];
106                 u=edge[cur[u]].t;
107             }
108         }
109     }
110     return flow;
111 }
112 int main()
113 {
114     int cas;
115     int option[101][101];
116     scanf("%d",&cas);
117     while(cas--)
118     {
119         s=0;t=4*n+1;
120         memset(option,0,sizeof(option));
121         scanf("%d%d%d",&n,&m,&k);
122         int u,v;
123         memset(head,-1,sizeof(head));
124         ent=0;
125         for(int i=1;i<=m;i++)
126         {
127             scanf("%d%d",&u,&v);
128             option[u][v]=1;
129             add(u,v+n,1);
130         }
131         if(k!=0)
132         {
133             for(int i=1;i<=n;i++)
134             {
135                 add(i,2*n+i,k);
136                 add(3*n+i,n+i,k);
137             }
138             for(int i=1;i<=n;i++)
139             {
140                 for(int j=1;j<=n;j++)
141                 {
142                     if(!option[i][j])
143                     {
144                         add(2*n+i,3*n+j,1);
145                     }
146                 }
147             }
148         }
149         for(int i=1;i<=n+1;i++)
150         {
151             for(int j=1;j<=n;j++)
152             {
153                 add(s,j,1);
154                 add(j+n,t,1);
155             }
156             if(dinic(s,t)!=n)
157             {
158                 printf("%d\n",i-1);
159                 break;
160             }
161         }
162     }
163     return 0;
164 }

View Code

 poj1815 相当水的一道最大流

题意加思路:

对于问至少删掉几个点使得S、T不联通,可以将每个点拆成i、i’两个点并连一条容量为1的i->i’的边,将其他关系依次补全后求最小割即可。

   
但是这个题目要求输出字典序最小的结果,那么就需要依次枚举每个点,如果删掉这个点之后最小割变小了,那么就说明这个点是最小割中的点,将其删除,否则就说名这个点不是最小割中的点,将其恢复。然后重复上面的操作就可以得到字典序最小的序列了。

不过这题为什么要拆点不容易想明白,我有点想法但又不知道怎么说,看来只好先记住了

代码:

新浦京www81707con 26新浦京www81707con 27

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 1000000
  8 #define MAXP 1024
  9 #define Max(a,b) a>b?a:b
 10 #define Min(a,b) a<b?a:b
 11 using namespace std;
 12 struct Edge
 13 {
 14     int s,t,f,next;
 15 } edge[MAXE];
 16 struct Edges
 17 {
 18     int t,next;
 19 } edges[MAXE];
 20 int head[MAXP];
 21 int isq[MAXP];
 22 int q[MAXP];
 23 int headedge[MAXP];
 24 int cur[MAXP];
 25 int pre[MAXP];
 26 int stack[MAXE];
 27 int ent,entedge;
 28 int n,a,b,s,t;
 29 void addedge(int start,int last)
 30 {
 31     edges[entedge].t=last;
 32     edges[entedge].next=headedge[start];
 33     headedge[start]=entedge++;
 34     edges[entedge].t=start;
 35     edges[entedge].next=headedge[last];
 36     headedge[last]=entedge++;
 37 }
 38 void add(int start,int last,int f)
 39 {
 40     edge[ent].s=start;
 41     edge[ent].t=last;
 42     edge[ent].f=f;
 43     edge[ent].next=head[start];
 44     head[start]=ent++;
 45     edge[ent].s=last;
 46     edge[ent].t=start;
 47     edge[ent].f=0;
 48     edge[ent].next=head[last];
 49     head[last]=ent++;
 50 }
 51 bool bfs(int S,int T)
 52 {
 53     memset(pre,-1,sizeof(pre));
 54     pre[S]=0;
 55     queue<int>q;
 56     q.push(S);
 57     while(!q.empty())
 58     {
 59         int temp=q.front();
 60         q.pop();
 61         for(int i=head[temp]; i!=-1; i=edge[i].next)
 62         {
 63             int temp2=edge[i].t;
 64             if(pre[temp2]==-1&&edge[i].f)
 65             {
 66                 pre[temp2]=pre[temp]+1;
 67                 q.push(temp2);
 68             }
 69         }
 70     }
 71     return pre[T]!=-1;
 72 }
 73 int dinic(int start,int last)
 74 {
 75     int flow=0,now;
 76     while(bfs(start,last))
 77     {
 78         int top=0;
 79         memcpy(cur,head,sizeof(head));
 80         int u=start;
 81         while(1)
 82         {
 83             if(u==last)//如果找到终点结束对中间路径进行处理并计算出该流
 84             {
 85                 int minn=INT_MAX;
 86                 for(int i=0; i<top; i++)
 87                 {
 88                     if(minn>edge[stack[i]].f)
 89                     {
 90                         minn=edge[stack[i]].f;
 91                         now=i;
 92                     }
 93                 }
 94                 for(int i=0; i<top; i++)
 95                 {
 96                     edge[stack[i]].f-=minn;
 97                     edge[stack[i]^1].f+=minn;
 98                 }
 99                 flow+=minn;
100                 top=now;
101                 u=edge[stack[top]].s;
102             }
103             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) //找出从u点出发能到的边
104                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
105                     break;
106             if(cur[u]==-1)//如果从该点未找到可行边,将该点标记并回溯
107             {
108                 if(top==0)break;
109                 pre[u]=-1;
110                 u=edge[stack[--top]].s;
111             }
112             else//如果找到了继续运行
113             {
114                 stack[top++]=cur[u];
115                 u=edge[cur[u]].t;
116             }
117         }
118     }
119     return flow;
120 }
121 int main()
122 {
123     while(~scanf("%d%d%d",&n,&a,&b))
124     {
125         memset(head,-1,sizeof(head));
126         ent=0;
127         entedge=0;
128         memset(headedge,-1,sizeof(headedge));
129         memset(isq,0,sizeof(isq));
130         s=0;
131         t=2*n+1;
132         add(s,a,INT_MAX);
133         add(b,t,INT_MAX);
134         add(a,a+n,INT_MAX);
135         int temp;
136         int ok=0;
137         for(int i=1; i<=n; i++)
138         {
139             if(i!=a&&i!=b)
140                 add(i,i+n,1);
141             for(int j=1; j<=n; j++)
142             {
143                 scanf("%d",&temp);
144                 if(i==a&&j==b&&temp)ok=1;
145                 if(temp&&i<j)
146                 {
147                     add(i+n,j,1);
148                     add(j+n,i,1);
149                     addedge(i,j);
150                 }
151             }
152         }
153         temp=dinic(s,t);
154         if(ok)printf("NO ANSWER!");
155         else
156         {
157             printf("%d\n",temp);
158             if(temp)
159             {
160                 for(int i=1; i<=n; i++)
161                 {
162                     if(i==a||i==b)continue;
163                     memset(head,-1,sizeof(head));
164                     ent=0;
165                     add(s,a,INT_MAX);
166                     add(b,t,INT_MAX);
167                     add(a,a+n,INT_MAX);
168                     for(int j=1; j<=n; j++)
169                     {
170                         if(j==i||isq[j])continue;
171                         if(j!=a&&j!=b)add(j,j+n,1);
172                         for(int k=headedge[j]; k!=-1; k=edges[k].next)
173                         {
174                             int temps=edges[k].t;
175                             if(isq[temps]||temps==i)continue;
176                             add(j+n,temps,1);
177                         }
178                     }
179                     if(dinic(s,t)==temp-1)
180                     {
181                         isq[i]=1;
182                         temp-=1;
183                     }
184                     if(temp==0)break;
185                 }
186                 int tot=0;
187                 for(int i=1; i<=n; i++)
188                 {
189                     if(isq[i])q[tot++]=i;
190                 }
191                 for(int i=0; i<tot-1; i++)
192                     printf("%d ",q[i]);
193                 printf("%d\n",q[tot-1]);
194             }
195         }
196     }
197     return 0;
198 }

View Code

 poj1422最小路径覆盖

题意:

    一个镇里所有的路都是单向路且不会组成回路。

       派一些伞兵去那个镇里,要到达所有的路口,有一些或者没有伞兵可以不去那些路口,只要其他人能完成这个任务。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

思路:答案就是先拆点二分图,然后输出路口总数-最大流,原因应该就是每个匹配能减少一个需求。

代码:

 

新浦京www81707con 28新浦京www81707con 29

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 920000
  8 #define MAXP 100010
  9 using namespace std;
 10 struct Edge
 11 {
 12     int s,t,f,next;
 13 };
 14 class Dinic
 15 {
 16 public:
 17     Dinic();
 18     void insert(int st,int tt,int f);
 19     bool bfs();
 20     void init(int st,int tt);
 21     int dinic();
 22     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 23     void dfs(int start);//在getCut中用来求出S
 24 private:
 25     int s,t;
 26     int ent;
 27     int flow;
 28     int *head;
 29     int *cur;
 30     int *pre;
 31     int *stack;
 32     Edge *edge;
 33     int *getS;
 34 };
 35 Dinic::Dinic()
 36 {
 37     head=new int[MAXP];
 38     cur=new int[MAXP];
 39     pre=new int[MAXP];
 40     stack=new int[MAXE];
 41     edge=new Edge[MAXE];
 42     getS=new int[MAXP];
 43 }
 44 void Dinic::init(int st,int tt)
 45 {
 46     memset(head,-1,sizeof(int)*MAXP);
 47     s=st;
 48     t=tt;
 49     ent=0;
 50     flow=0;
 51 }
 52 void Dinic::insert(int st,int tt,int f)
 53 {
 54     edge[ent].s=st;
 55     edge[ent].t=tt;
 56     edge[ent].f=f;
 57     edge[ent].next=head[st];
 58     head[st]=ent++;
 59     edge[ent].s=tt;
 60     edge[ent].t=st;
 61     edge[ent].f=0;
 62     edge[ent].next=head[tt];
 63     head[tt]=ent++;
 64 }
 65 bool Dinic::bfs()
 66 {
 67     memset(pre,-1,sizeof(int)*MAXP);
 68     pre[s]=0;
 69     queue<int>q;
 70     q.push(s);
 71     while(!q.empty())
 72     {
 73         int temp1=q.front();
 74         q.pop();
 75         for(int i=head[temp1]; i!=-1; i=edge[i].next)
 76         {
 77             int temp2=edge[i].t;
 78             if(pre[temp2]==-1&&edge[i].f)
 79             {
 80                 pre[temp2]=pre[temp1]+1;
 81                 q.push(temp2);
 82             }
 83         }
 84     }
 85     return pre[t]!=-1;
 86 }
 87 int Dinic::dinic()
 88 {
 89     int now;
 90     while(bfs())
 91     {
 92         int top=0;
 93         memcpy(cur,head,sizeof(int)*MAXP);
 94         int u=s;
 95         while(1)
 96         {
 97             if(u==t)
 98             {
 99                 int minn=INT_MAX;
100                 for(int i=0; i<top; i++)
101                 {
102                     if(minn>edge[stack[i]].f)
103                     {
104                         minn=edge[stack[i]].f;
105                         now=i;
106                     }
107                 }
108                 for(int i=0; i<top; i++)
109                 {
110                     edge[stack[i]].f-=minn;
111                     edge[stack[i]^1].f+=minn;
112                 }
113                 flow+=minn;
114                 top=now;
115                 u=edge[stack[top]].s;
116             }
117             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
118                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
119                     break;
120             if(cur[u]==-1)
121             {
122                 if(top==0)break;
123                 pre[u]=-1;
124                 u=edge[stack[--top]].s;
125             }
126             else
127             {
128                 stack[top++]=cur[u];
129                 u=edge[cur[u]].t;
130             }
131         }
132     }
133     return flow;
134 }
135 void Dinic::getCut()
136 {
137     memset(getS,0,sizeof(int)*MAXP);
138     getS[s]=1;
139     dfs(s);
140     for(int i=0; i<MAXP; i++)
141     {
142         if(getS[i])
143             cout<<i<<" ";
144     }
145     cout<<endl;
146 }
147 void Dinic::dfs(int start)
148 {
149     for(int i=head[start]; i!=-1; i=edge[i].next)
150     {
151         if(edge[i].f)
152         {
153             int temp=edge[i].t;
154             if(!getS[temp])
155             {
156                 getS[temp];
157                 dfs(temp);
158             }
159         }
160     }
161 }
162 int main()
163 {
164     int cas,n,m,s,t,f;
165     Dinic *temp=new Dinic();
166     scanf("%d",&cas);
167     while(cas--)
168     {
169         scanf("%d%d",&n,&m);
170         temp->init(0,2*n+1);
171         for(int i=1; i<=n; i++)
172         {
173             temp->insert(0,i,1);
174             temp->insert(i+n,2*n+1,1);
175         }
176         for(int i=0; i<m; i++)
177         {
178             scanf("%d%d",&s,&t);
179             temp->insert(s,t+n,1);
180         }
181         cout<<(n-temp->dinic())<<endl;
182     }
183     delete temp;
184     return 0;
185 }

View Code

 zoj3229

题意:

一个屌丝给m个女神拍照,计划拍照n天,每一天屌丝给给定的C个女神拍照,每天拍照数不能超过D张,而且给每个女神i拍照有数量限制[Li,Ri],对于每个女神n天的拍照总和不能少于Gi,如果有解求屌丝最多能拍多少张照,并求每天给对应女神拍多少张照;否则输出-1。

本来这题我是不想写博客的,毕竟这是我拿来学习的,然而因为一个坑,还是准备写一下,也许还能给别人一点提醒呢

这题的输出既不是输出屌丝每天给每个女神拍照的数量,也不是如果某天给某人拍照数量是0就不输出,而是只要题目中给出了就要输出,如果题目中没有给出就不输出。

代码:

 

新浦京www81707con 30新浦京www81707con 31

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 900000
  8 #define MAXP 2222
  9 using namespace std;
 10 int temps[400][1010];
 11 int id[400][1410];
 12 int flows[400][1500];
 13 struct Edge
 14 {
 15     int s,t,f,next;
 16 };
 17 class Dinic
 18 {
 19 public:
 20     Dinic();
 21     void init(int st,int tt);//初始化私有成员
 22     void insert(int st,int tt,int f);//普通最大流插入边
 23     void add_low_up(int st,int tt,int low,int up,int sign);//有上下界最大流插入边,其中sign是用来记录一些点对应的边
 24     void deel();//有上下界最大流后期连超级源汇
 25     bool bfs();//搜索增广路径
 26     void dinic();//非递归求最大流
 27     void reset(int st,int tt);//重置源汇
 28     bool is_True();//判断是否存在满足上下界的最大流
 29     void print_path(int a,int b,int c,int d);//视题目要求进行输出路径或者之类的处理
 30     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 31     void dfs(int start);//在getCut中用来求出S
 32 private:
 33     int s,t;
 34     int ent;
 35     int flow;
 36     int *head;
 37     int *cur;
 38     int *pre;
 39     int *stack;//非递归dinic中模拟栈
 40     Edge *edge;
 41     int *getS;//纪录S;
 42     int *degree;//有源汇有上下界最大流中使用,记录每个点的度数
 43     int sum;//有源汇有上下界最大流中使用,纪录附加边满流时的流量
 44 };
 45 Dinic::Dinic()
 46 {
 47     head=new int[MAXP];
 48     cur=new int[MAXP];
 49     pre=new int[MAXP];
 50     stack=new int[MAXE];
 51     edge=new Edge[MAXE];
 52     getS=new int[MAXP];
 53     degree=new int[MAXP];
 54 }
 55 void Dinic::init(int st,int tt)
 56 {
 57     memset(head,-1,sizeof(int)*MAXP);
 58     memset(degree,0,sizeof(int)*MAXP);
 59     s=st;
 60     t=tt;
 61     ent=0;
 62     flow=0;
 63     sum=0;
 64 }
 65 void Dinic::insert(int st,int tt,int f)
 66 {
 67     edge[ent].s=st;
 68     edge[ent].t=tt;
 69     edge[ent].f=f;
 70     edge[ent].next=head[st];
 71     head[st]=ent++;
 72     edge[ent].s=tt;
 73     edge[ent].t=st;
 74     edge[ent].f=0;
 75     edge[ent].next=head[tt];
 76     head[tt]=ent++;
 77 }
 78 void Dinic::add_low_up(int st,int tt,int low,int up,int sign)
 79 {
 80     degree[st]-=low,degree[tt]+=low;
 81     insert(st,tt,up-low);
 82     if(sign)id[st][tt]=ent-1;
 83 }
 84 void Dinic::deel()
 85 {
 86     for(int i=0; i<s; i++)
 87     {
 88         if(degree[i]<0)
 89             insert(i,t,-degree[i]);
 90         else sum+=degree[i],insert(s,i,degree[i]);
 91     }
 92 }
 93 bool Dinic::bfs()
 94 {
 95     memset(pre,-1,sizeof(int)*MAXP);
 96     pre[s]=0;
 97     queue<int>q;
 98     q.push(s);
 99     while(!q.empty())
100     {
101         int temp1=q.front();
102         q.pop();
103         for(int i=head[temp1]; i!=-1; i=edge[i].next)
104         {
105             int temp2=edge[i].t;
106             if(pre[temp2]==-1&&edge[i].f)
107             {
108                 pre[temp2]=pre[temp1]+1;
109                 q.push(temp2);
110             }
111         }
112     }
113     return pre[t]!=-1;
114 }
115 void Dinic::dinic()
116 {
117     int now;
118     while(bfs())
119     {
120         int top=0;
121         memcpy(cur,head,sizeof(int)*MAXP);
122         int u=s;
123         while(1)
124         {
125             if(u==t)
126             {
127                 int minn=INT_MAX;
128                 for(int i=0; i<top; i++)
129                 {
130                     if(minn>edge[stack[i]].f)
131                     {
132                         minn=edge[stack[i]].f;
133                         now=i;
134                     }
135                 }
136                 for(int i=0; i<top; i++)
137                 {
138                     edge[stack[i]].f-=minn;
139                     edge[stack[i]^1].f+=minn;
140                 }
141                 flow+=minn;
142                 top=now;
143                 u=edge[stack[top]].s;
144             }
145             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
146                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
147                     break;
148             if(cur[u]==-1)
149             {
150                 if(top==0)break;
151                 pre[u]=-1;
152                 u=edge[stack[--top]].s;
153             }
154             else
155             {
156                 stack[top++]=cur[u];
157                 u=edge[cur[u]].t;
158             }
159         }
160     }
161 }
162 void Dinic::reset(int st,int tt)
163 {
164     s=st,t=tt;
165     flow=0;
166 }
167 bool Dinic::is_True()
168 {
169     deel();
170     dinic();
171     if(sum==flow)
172     {
173         head[s]=-1,head[t]=-1;
174         reset(0,s-1);
175         dinic();
176         return true;
177     }
178     else return false;
179 }
180 void Dinic::print_path(int a,int b,int c,int d)
181 {
182     if(is_True())//有满足上下界的最大流
183     {
184         printf("%d\n",flow);
185         memset(flows,0,sizeof(flows));
186         /*for(int i=a;i<=b;i++)
187             for(int j=c;j<=d;j++)
188                 if(id[i][j])
189                     printf("%d\n",temps[i][j-b]+edge[id[i][j]].f);*/
190         for(int i=a;i<=b;i++)
191         {
192             for(int j=head[i];j!=-1;j=edge[j].next)
193             {
194                 int temp=edge[j].t;
195                 if(temp>=c&&temp<=d)
196                 {
197                     flows[i][temp]+=edge[j^1].f;
198                 }
199             }
200         }
201         for(int i=a;i<=b;i++)
202         {
203             for(int j=c;j<=d;j++)
204             {
205                 if(temps[i][j-b]!=-1)
206                     printf("%d\n",flows[i][j]+temps[i][j-b]);
207             }
208         }
209     }
210     else//没有符合上下界的最大流
211         printf("-1\n");
212     printf("\n");
213 }
214 void Dinic::getCut()
215 {
216     memset(getS,0,sizeof(int)*MAXP);
217     getS[s]=1;
218     dfs(s);
219     for(int i=0; i<MAXP; i++)
220     {
221         if(getS[i])
222             printf("%d ",i);
223     }
224     printf("\n");
225 }
226 void Dinic::dfs(int start)
227 {
228     for(int i=head[start]; i!=-1; i=edge[i].next)
229     {
230         if(edge[i].f)
231         {
232             int temp=edge[i].t;
233             if(!getS[temp])
234             {
235                 getS[temp];
236                 dfs(temp);
237             }
238         }
239     }
240 }
241 int main()
242 {
243     int n,m,num,no,low,up,s,t;
244     Dinic *temp=new Dinic();
245     while(~scanf("%d%d",&n,&m))
246     {
247         memset(id,0,sizeof(id));
248         memset(temps,-1,sizeof(temps));
249         s=0,t=n+m+1;
250         temp->init(t+1,t+2);
251         for(int i=1; i<=m; i++)
252         {
253             scanf("%d",&num);
254             temp->add_low_up(n+i,t,num,INT_MAX,0);
255         }
256         for(int i=1; i<=n; i++)
257         {
258             scanf("%d%d",&num,&up);
259             temp->insert(s,i,up);
260             for(int j=1; j<=num; j++)
261             {
262                 scanf("%d%d%d",&no,&low,&up);
263                 temp->add_low_up(i,no+1+n,low,up,1);
264                 temps[i][no+1]=low;
265             }
266         }
267         temp->insert(t,s,INT_MAX);
268         temp->print_path(1,n,n+1,n+m);
269     }
270     delete temp;
271     return 0;
272 }

View Code

 

poj3692

题意:已知班级有g个女孩和b个男孩,所有女生之间都相互认识,所有男生之间也相互认识,给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个团,使得里面所有人都认识,求此团最大人数。

 思路:这一题的思路还是很巧妙的,他的答案就是这个图的补图的最大点权独立集,因为补图中的独立集就是原图中二分图中都有关系的点集,本人表示没想到,看的题解。

 

代码:

新浦京www81707con 32新浦京www81707con 33

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<climits>
  7 #define MAXE 920000
  8 #define MAXP 100010
  9 using namespace std;
 10 struct Edge
 11 {
 12     int s,t,f,next;
 13 };
 14 class Dinic
 15 {
 16 public:
 17     Dinic();
 18     void insert(int st,int tt,int f);
 19     bool bfs();
 20     void init(int st,int tt);
 21     int dinic();
 22     void getCut();//获取割边S,先使用dinic获取最大流之后使用
 23     void dfs(int start);//在getCut中用来求出S
 24 private:
 25     int s,t;
 26     int ent;
 27     int flow;
 28     int *head;
 29     int *cur;
 30     int *pre;
 31     int *stack;
 32     Edge *edge;
 33     int *getS;
 34 };
 35 Dinic::Dinic()
 36 {
 37     head=new int[MAXP];
 38     cur=new int[MAXP];
 39     pre=new int[MAXP];
 40     stack=new int[MAXE];
 41     edge=new Edge[MAXE];
 42     getS=new int[MAXP];
 43 }
 44 void Dinic::init(int st,int tt)
 45 {
 46     memset(head,-1,sizeof(int)*MAXP);
 47     s=st;
 48     t=tt;
 49     ent=0;
 50     flow=0;
 51 }
 52 void Dinic::insert(int st,int tt,int f)
 53 {
 54     edge[ent].s=st;
 55     edge[ent].t=tt;
 56     edge[ent].f=f;
 57     edge[ent].next=head[st];
 58     head[st]=ent++;
 59     edge[ent].s=tt;
 60     edge[ent].t=st;
 61     edge[ent].f=0;
 62     edge[ent].next=head[tt];
 63     head[tt]=ent++;
 64 }
 65 bool Dinic::bfs()
 66 {
 67     memset(pre,-1,sizeof(int)*MAXP);
 68     pre[s]=0;
 69     queue<int>q;
 70     q.push(s);
 71     while(!q.empty())
 72     {
 73         int temp1=q.front();
 74         q.pop();
 75         for(int i=head[temp1]; i!=-1; i=edge[i].next)
 76         {
 77             int temp2=edge[i].t;
 78             if(pre[temp2]==-1&&edge[i].f)
 79             {
 80                 pre[temp2]=pre[temp1]+1;
 81                 q.push(temp2);
 82             }
 83         }
 84     }
 85     return pre[t]!=-1;
 86 }
 87 int Dinic::dinic()
 88 {
 89     flow=0;
 90     int now;
 91     while(bfs())
 92     {
 93         int top=0;
 94         memcpy(cur,head,sizeof(int)*MAXP);
 95         int u=s;
 96         while(1)
 97         {
 98             if(u==t)
 99             {
100                 int minn=INT_MAX;
101                 for(int i=0; i<top; i++)
102                 {
103                     if(minn>edge[stack[i]].f)
104                     {
105                         minn=edge[stack[i]].f;
106                         now=i;
107                     }
108                 }
109                 for(int i=0; i<top; i++)
110                 {
111                     edge[stack[i]].f-=minn;
112                     edge[stack[i]^1].f+=minn;
113                 }
114                 flow+=minn;
115                 top=now;
116                 u=edge[stack[top]].s;
117             }
118             for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)
119                 if(edge[i].f&&pre[edge[i].t]==pre[u]+1)
120                     break;
121             if(cur[u]==-1)
122             {
123                 if(top==0)break;
124                 pre[u]=-1;
125                 u=edge[stack[--top]].s;
126             }
127             else
128             {
129                 stack[top++]=cur[u];
130                 u=edge[cur[u]].t;
131             }
132         }
133     }
134     return flow;
135 }
136 void Dinic::getCut()
137 {
138     memset(getS,0,sizeof(int)*MAXP);
139     getS[s]=1;
140     dfs(s);
141     for(int i=0;i<MAXP;i++)
142     {
143         if(getS[i])
144             cout<<i<<" ";
145     }
146     cout<<endl;
147 }
148 void Dinic::dfs(int start)
149 {
150     for(int i=head[start];i!=-1;i=edge[i].next)
151     {
152         if(edge[i].f)
153         {
154             int temp=edge[i].t;
155             if(!getS[temp])
156             {
157                 getS[temp];
158                 dfs(temp);
159             }
160         }
161     }
162 }
163 int mp[210][210];
164 int main()
165 {
166     int n,m,k,s,t;
167     int tot=0;
168     Dinic *temp = new Dinic();
169     while(~scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
170     {
171         memset(mp,-1,sizeof(mp));
172         for(int i=1;i<=k;i++)
173         {
174             scanf("%d%d",&s,&t);
175             mp[s][t]=0;
176         }
177         cout<<"Case "<<(++tot)<<": ";
178         temp->init(0,n+m+1);
179         for(int i=1;i<=n;i++)
180         {
181             temp->insert(0,i,1);
182             for(int j=1;j<=m;j++)
183             {
184                 if(mp[i][j])
185                     temp->insert(i,j+n,1);
186             }
187         }
188         for(int i=1;i<=m;i++)
189             temp->insert(i+n,n+m+1,1);
190         printf("%d\n",n+m-temp->dinic());
191     }
192     delete temp;
193     return 0;
194 }

View Code

 

相关文章