【网络流】一点点更新

Mr.OneSong — Sun, 16 Sep 2012 00:46:00 GMT

今天做题的时候碰到了一道网络流的题竟然没有做出来，甚至到现在还是没有弄懂的囧，实在是惭愧，所以现在好好理理网络流了o(╯□╰)o。
hdu1532
题意：纯求最大流。
题解：以1为源点，n为汇点建边。
hdu1533
题意：在一个栅格地图上有n个的小男人和n个房子，在每一个单位时间内每个小的人可以移动一个单位的一步到相邻的点，无论是水平的还是垂直的。对于每一个小人，他每移动一步，你需要支付1美元的旅行费用，直到他进入一所房子。限制条件是每间房子只能容纳一个小人。你的任务是计算发送这n个不同的小人到n个不同的房屋所需要支付的最低金额。
题解：最小费用流。该题中距离的定义是两点横坐标差的绝对值和纵坐标差的绝对值之和，并且我们可以看到小人的数目和房子的数目是相等的（设为n），则我们将每个小人与每个房子之间建立一条容量为1，费用为彼此之间距离（是按照上述定义的距离）的流；同时我们设定一个超级源和超级汇，从超级源连接到每一个小人容量为1，费用为0的流；从每个房子连到超级汇一条容量为1，费用为0的流，最火从超级源到超级汇求一下最小费用流即得到答案。

今天就到这里了，谢谢关心: ） 2012/9/6 8:55 by Mr.一首歌

Mr.OneSong 2012-09-16 08:46 发表评论

【计算几何】一点点更新

Mr.OneSong — Sat, 08 Sep 2012 14:20:00 GMT

摘要: 【背景】话说Mr.一首歌根本不会计算几何此等神物啊，但是当小学妹问起自己凸包神马的东西时，自己幸好还收藏着一个模版，于是就给了人家模版看，叫人家看懂ｇｒａｈａｍ思想后再来交流，这才发现要开始好好学计算几何了（此等动机不纯，小朋友们千万不要学我这个坏榜样）。１.基础❤多边形重心的计算求多边形重心的题目大致有这么几种： 1、质量集中在顶点上 n个顶点坐标为(xi,yi)，质量为mi，则重心　　X =... 阅读全文

Mr.OneSong 2012-09-08 22:20 发表评论

【稳定婚姻问题】

Mr.OneSong — Fri, 07 Sep 2012 17:55:00 GMT

摘要: 【完备婚姻问题】背景：现在有ｎ为大龄未婚男和ｎ位大龄未婚女，他们为了应父母之命，完成结婚生子的神圣使命，义然决定进行相亲。每一位男生（女生）都和其余的每一位女生（男生）碰过了面，并且根据彼此的谈话对对方产生了一定的好感，但是每个男生（女生）对每一个女生（男生）的喜好成度是不同的，所以他们回去后都对这ｎ个女生（男生）按喜好程度进行了排名。每个男生（女生）都希望能够得到他喜好度最高的作... 阅读全文

Mr.OneSong 2012-09-08 01:55 发表评论

一般预流推进算法（课本神马的都弱爆了）

Mr.OneSong — Fri, 24 Aug 2012 02:42:00 GMT

　书上所说的一般预流推进算法往往涉及很多概念比较繁琐，下面我按照自己的理解，通过一道简单的习题，来讲述一下一般预流推进算法，可能有不正确的地方，希望有大神能够给我指点。
　现在假设读者已经了解了网络流的基本概念和一般增广路算法。
　以单源汇网络流为例，最大流求的是单位时间内能够从源点Ｓ流到汇点Ｔ的最大流量（容量）。但是一般增广路算法实现相当麻烦。因为这种方法必须每次找一条增广路，然后沿着这条增广路进行增广，这就好像一开始所有的汽车全部被堵在了源点Ｓ，（假设这些汽车都迫切到达汇点Ｔ），然后一般增广路算法的实现就好像一名交警从源点Ｓ随便走了某一条路线到达了汇点Ｔ，发现这条路线上所有的线段的权值最小值是某个确定的值Limit,然后交警返回到原点Ｓ，汇报了他的结果：从Ｓ到Ｔ沿着他刚才走过的路径同时开可以“畅通无阻”不堵车，然后第二个交警从Ｓ开出走了另一条与之前那个交警不完全相同的路线到达Ｔ，回来报告了沿着他刚才走过的路径同时开Limit'辆车可以“畅通无阻”不堵车，如此循环，直到最后一名交警走完了最后一条能够到达Ｔ的路线回来汇报结果，交警长官最终得到一个结论：前面Limit辆车走第一条路线，接下来Limit'辆车走第二条路线，接下来。。。。。。
　是不是觉得这样做有些繁琐呢？虽然这种方法实现起来比较容易理解，但是这种方法等于用深度优先搜索（ＤＦＳ）吧所有情况都搜索了一遍，太耗时了！
　有没有优化的方法？其实交警长官可以派若干个交警驻守在各个交叉路口，并且交警长官采取了无为而治的策略。那么，现在假设和交叉口Ｓ隔着一条街相邻的交叉路口只有Ｓ１和Ｓ２，连接Ｓ和Ｓ１的街最多能同时开过３辆车，连接Ｓ和Ｓ２的街最多能同时开过８辆车，那么我们现在就可以直接让３辆车从Ｓ开到Ｓ１，直接让８辆车从Ｓ开到Ｓ２，因为Ｓ１，Ｓ２这些交点都有交警把守，他们也会像Ｓ点处的交警一样进行处理，那么最后能够到达Ｔ的车的单位时间的辆数＝∑min(Si,Pi),其中Ｓｉ表示所有和Ｔ直接一条线段相连的交点，Ｐｉ是Ｓｉ和Ｔ之间的那条线段的最大容量。
　这就是一般预流推进算法的Mr.OneSong描述。
　我们首先分析的是源点，其次分析的是源点能够到达的所有点。因为我们不可能让这“所有点”在同一时间被处理，所以我们将这些待处理的点加入到队列中，因为考虑到多个中间源点到达同一个中间汇点的情况，所以有些点需要多次进队列：
　那么对于什么情况需要将一点加入队列或者重新加入队列呢？其实只有两种情况：
　　 ①当从某一点S'流到所有的和S'相连的Ti'时,如果S'还有残余流量，S'将进队列，因为这个时候S'中还存有一种“势能”，所以他还有往后流的可能
　　 ②当从某一点S'流到和S'相连的某一点Ti'时，因为S'把他的一部分残留流量给了T',所以T'从某种意义上来说变成了和S'一样的点，需要将其代入队列中进行分析　
　如果按照上述的方法，虽然现实当中司机师傅都能很好的保证汽车最大的通过量，但是在电脑模拟起来可能会造成一些问题，比如说一辆车从Ｓｉ点开到Ｓｊ点后发现从Ｓｊ点也行不同，于是又开到了Ｓｉ，于是一直在Ｓｉ和Ｓｊ之间陷入了循环。有很多方法能够解决这个矛盾,所以这里用一个残留量函数RE[i][j]表示所有连接Ｓｉ到Ｓｊ的所有线路的流量总和：比如说对走过的路径进行标记，标记结果就是对满流的线段更新其可残留量为０，不满流的其残留量相应减少；同时我们用一般预流推进算法实现的是类似广度优先搜索（ＢＦＳ）的算法，不能像ＤＦＳ一样很好的标记和撤销标记，所以这里我们用一个势能函数H[]来确定流是否可行。
　初始时设源点的势能函数H[S]=V'>=V-1(V代表顶点数),这是为了确保Ｓ的势能能够确保Ｓ上的流能够到达图上的所有其他V-1个点；其他点的势能函数H[i]=0。
　规定两点Ｓｉ能够将其上的残留流量流到与其临接的Ｓｊ上当且仅当下面两种情况的其中一种成立：Ｓｉ＝＝Ｓ或H[i] - H[j] == 1。这样就保证了该算法陷入死循环。

例题：输入图的边数Ｅ和点数Ｖ，接下来每行３个数表示各边的起点，终点和该边的最大流量，求从１为源点到Ｖ为汇点的最大流。
样例输入：
4 4
1 2 2
1 3 3
2 4 1
3 4 6
样例输出：
4

#include <stdio.h>
#include <queue>
using namespace std;
#define oo (1<<29)
const int maxn = 110;
int n , m;
int RE[maxn][maxn] , EF[maxn] , H[maxn];
int S , T , Max_Flow;
queue<int> Q;

int min(int a , int b)
{
    return a < b ? a : b;
}

void init()
{
    Max_Flow = 0;
    S = 1; T = n;
    int i;
    H[S] = n;
    EF[S] = oo;
    EF[T] = -oo;
}

void Push(int Si)
{
    int i , Tmp;
    for(i=1;i<=n;i++)
    {
        Tmp = min(RE[Si][i] , EF[Si]);
        if(Tmp > 0 && (Si == S || H[Si] - H[i] == 1))
        {
            RE[Si][i] -= Tmp; RE[i][Si] += Tmp;
            EF[Si] -= Tmp; EF[i] += Tmp;
            if(i == T) Max_Flow +=Tmp;
            if(i != T && i != S) Q.push(i);
        }
    }
    return;
}

void Relabel(int Si)
{
    if(Si != S && Si != T && EF[Si] > 0)
    {
        H[Si] ++;
        Q.push(Si);
    }
    return;
}

void Push_Relabel()
{
    int Si;
    init();
    Q.push(S);
    while(!Q.empty())
    {
        Si = Q.front();
        Q.pop();
        Push(Si);
        Relabel(Si);
    }
    printf("%d\n",Max_Flow);
}

int main()
{
    freopen("pushrelabelin.txt","r",stdin);
    freopen("pushrelabelout.txt","w",stdout);
    scanf("%d%d",&m,&n);
    init();
    int i;
    int u , v , w;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        RE[u][v] += w;
    }
    Push_Relabel();
    return 0;
}

Mr.OneSong 2012-08-24 10:42 发表评论

C++博客-Mr.一首歌

【网络流】一点点更新

【计算几何】一点点更新

【稳定婚姻问题】

一般预流推进算法（课本神马的都弱爆了）