新普金娱乐网址


算法笔记_190:历届试题 幸运数(Java)

数学JavaScript与Lisp,通向编程圣殿[1]: “树”的根底测算

极端充分流动, 最小割问题同算法实现

  • 十月 03, 2018
  • 数学
  • 没有评论

本博客采用创作并用版权协议, 要求签署、非商业用途以及保持一致.
转载本博客文章要为按照签字-非经贸用途-保持一致的编并用协议.

村办博客:doubleq.win

由博文被富含部分LaTex格式数学公式, 在简书中形不好,
所以推荐阅读博客中的本不过特别流动,
最小割基本问题与算法实现

于极端可怜流动最小割问题之总, 如发生错误, 欢迎指出.

1142 奖学金

 

2007年NOIP全国联赛普及组

 时间限制: 1
s

 空间范围: 128000
KB

 题目等级 : 白银
Silver

题解

 

 

 

题目叙述 Description

某个小学最近获了一如既往笔画赞助,打算用出里面一些吧学习成绩优秀之前头5称学生发奖学金。期末,每个学员都起3门课的实绩:语文、数学、英语。先随总分从赛至低位排序,如果个别单同学总分一样,再比如语文成绩由大顶小排序,如果少独同学总分和语文成绩都同,那么规定学号小的同桌消除在前面,这样,每个学员的排序是唯一确定的。

职责:先冲输入的3山头课的实绩计算总分,然后照上述规则排序,最后仍排名依次输出前5称呼学生的学号和总分。注意,在前头5名叫校友受,每个人之奖学金都非同等,因此,你必须严厉以上述规则排序。例如,在有正确答案中,如果前少履行的出口数据(每行输出两独数:学号、总分)是:

7 279

5 279

及时简单尽数据的含义是:总分最高的蝇头单同学的学号依次是7哀号、5哀号。这片名叫同班的总分都是279(总分等于输入的语文、数学、英语三科成绩的同),但学号为7之学生语文成绩再次强一些。如果您的前少曰的输出数据是:

5 279

7 279

尽管如此随出口错误处理,不能够得分。

输入描述 Input Description

包含n+1行:

第1作为一个恰好整数n,表示学校与评选的学童人数。

第2到n+1实践,每行有3个用空格隔开的数字,每个数字都在0到100间。第j尽的3独数字依次表示学号为j-1之学生的语文、数学、英语的成。每个学生的学号按照输入顺序号为1~n(恰好是输入数据的行号减1)。

出口描述 Output Description

共有5执,每行是零星个用空格隔开的正整数, 依次表示前5叫做学员的学号和总分。

样例输入 Sample Input

6

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98

样例输出 Sample Output

6 265

4 264

3 258

2 244

1 237

数范围和提示 Data Size & Hint

50%底数满足:各学生的总成绩各不相同

100%的数码满足:6<=n<=300

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 struct student
 5 {
 6     int xh;//学号
 7     int yw;
 8     int sx;
 9     int yy;
10     int zf; 
11 }a[10001];
12 int comp(const student & a,const student & b)
13 {
14     if(a.zf>b.zf)return 1;
15     if(a.zf<b.zf)return 0;
16     if(a.yw>b.yw)return 1;
17     if(a.yw<b.yw)return 0;
18     if(a.xh<b.xh)return 1;
19     return 0;
20 }
21 int main()
22 {
23     int n;
24     cin>>n;
25     for(int i=1;i<=n;i++)
26     {
27         cin>>a[i].yw>>a[i].sx>>a[i].yy;
28         a[i].zf=a[i].yw+a[i].sx+a[i].yy;
29         a[i].xh=i;
30     }
31     sort(a+1,a+n+1,comp);
32     for(int i=1;i<=5;i++)
33     {
34         cout<<a[i].xh<<" "<<a[i].zf<<endl;
35     }
36     return 0;
37 }

 

最大流(MaxFlow)问题

加指定的一个出往图,其中有点儿个独特之点源S(Sources)和汇T(Sinks),每条边发指定的容量(Capacity),求满足条件的从S到T的极特别流动(MaxFlow).

想像一长条多长不同水流量的水管成的大网, s为供水广, t也水用户,
最充分流动问题就是是找到会以s到t流通的无限可怜水流量

一个淌是最酷流当且只当那留网络不含其他增广路径(里面的名号在后有详细分解)

流(Flow)的骨干特性

设$C_{uv}$代表边u及v最酷允许流量(Capacity),
$f_{uv}$代表u到v的目前流量, 那么有瞬间星星独特性:

  • $(u, v)$为来往图边, $0<=f_{uv}<=C_{uv}$, 即对于有的底限,
    当前流量不允许超过该Capacity
  • 除开$s, t$之外, 对具有节点有 $\sum\limits_{(v, u)}f_{wu} =
    \sum\limits_{(u, v)}f_{uv}$, 即对于另外一样接触,
    流入该点的流量当留起该点的流量,
    流量守恒原则(类似与能量守恒的概念).

非负数值$f(u, v)$为从节点u到节点v的流.一个流$|f|$的定义:
$$|f| = \sum\limits_{v \in V}f(s,v) – \sum\limits_{v \in V}f(v,
s)$$

最好充分流动问题不怕要找到一个最大的流f

Ford-Fulkerson方法

用称为方法, 而休是算法,
因为FF(Ford-Fulkerson简称)包含不同运行时之几种植实现,
是平等种迭代的方法.

拖欠措施要借助让残存网络, 增广路径和割

//伪代码
初始化:所有流f = 0
while 在残存网络中存在增广路径p
    增加流f的值
return f

遗留网络

为定网络G和流量f, 残存网络$G_f$由那些本时有发生空间对流量进行调整的边构成.

留网络 = 容量网络capacity – 流量网络flow

图片 1

剩网络

增广路径

增广路径p是留网络被平等漫漫由源节点s到聚集点t的简易路径,在相同条长广路径p上能为各个条边增的流量的极充分价值吗路径p的残存容量$c_f(p)
= min \{c_f(u,v):(u,v) \in p \}$

每当平等长长广路径p上, 要追加整条增广路径的水流量,
则必须看尽小会接受水流量的管道, 不然水管会爆掉,
这顶小受水流量就是残存容量

于有往图网络G中, 割(S, T)将V划分也S和T = V – S, 使得s属于S集合,
t属于T集合. 割(S, T)的容量是据从集合S到集合T所有边的容量的和.

图片 2

最大流

最好可怜流动最小割理论

设$f$为流动网络G = (V, E)中之一个流动, 该流网络的源节点为s, 汇点为t,
则下面的基准是当价格的:

  • f是G的一个最为要命流动
  • 剩网络$G_f$不包含其他增广路径
  • $|f| = c(S, T)$, 其中(S, T)是流网络G的有割

Ford-Fulkerson算法Java实现

伪代码

for each edge(u, v)属于G.E(图G的边)
    (u, v).f = 0  //所有边的流为0
//循环终止条件为残存我昂罗中不存在增广路径
while s到t的残存网络中存在增广路径p:
    c(p) = 最小残存容量
    for 增广路径的每条边
        if 这条边属于E集合
            (u, v).f = (u, v).f + c(p)  //意思是在原有的流增加最小残存容量.
        else
            (u, v).f = (u, v).f - c(p)

//边的定义
public class FlowEdge {
    private final int v, w;  //边的起点和终点
    private final double capacity;  //流量
    private double flow;   //流
    public FlowEdge(int v, int w, double capacity) {
        this.v = v;
        this.w = w;
        this.capacity = capacity;
    }
    public int from() {
        return v;
    }
    public int to() {
        return w;
    }
    public double capacity() {
        return capacity;
    }
    public double flow() {
        return flow;
    }
    public int other(int vertex) {
        if (vertex == v) {
            return w;
        } else if (vertex == w) {
            return v;
        } else {
            throw new RuntimeException("Inconsistent edge");
        }
    }
    //v中残留流量
    public double residualCapacityTo(int vertex) {
        if (vertex == v) {  //反向边
            return flow;
        } else if (vertex == w) {  //正向边
            return capacity - flow;
        } else {
            throw new IllegalArgumentException();
        }
    }
    //向v中增加delta
    public void addResidualFlowTo(int vertex, double delta) {
        if (vertex == v) {
            flow -= delta;
        } else if (vertex == w) {
            flow += delta;
        } else {
            throw new IllegalArgumentException();
        }
    }
}

//流图的定义
public class FlowNetwork {
    private final int V;  //顶点个数
    private Bag<FlowEdge>[] adj;
    public FlowNetwork(int V) {
        this.V = V;
        adj = (Bag<FlowEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<>();
        }
    }
    //想流图中增加边
    public void addEdge(FlowEdge e) {
        int v = e.from();
        int w = e.to();
        adj[v].add(e);  //正向边
        adj[w].add(e);  //反向边
    }
    public int V() {
        return V;
    }
    public Iterable<FlowEdge> adj(int v) {  //返回邻接边
        return adj[v];
    }
}

//FordFulkerson方法的实现
public class FordFulkerson {
    private boolean[] marked;  //如果残留网络中有s->v路径, 则为true
    private FlowEdge[] edgeTo;  //s->v路径的最后的边
    private double value; //流

    public FordFulkerson(FlowNetwork G, int s, int t) {
        value = 0.0;
        //当找不到增广路径时终止
        while (hasAugmentingPaht(G, s, t)) {  //判断是否还有增广路径
            double bottle = Double.POSITIVE_INFINITY;
            for (int v = t; v != s; v = edgeTo[v].other(v)) {  //计算最大流量
                bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
            }
            for (int v = t; v != s; v = edgeTo[v].other(v)) {
                edgeTo[v].addResidualFlowTo(v, bottle);
            }
            value += bottle;
        }
    }
    private boolean hasAugmentingPaht(FlowNetwork G, int s, int t) {
        edgeTo = new FlowEdge[G.V()];
        marked = new boolean[G.V()];

        Queue<Integer> q = new Queue<>();
        q.enqueue(s);
        marked[s] = true;
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (FlowEdge e : G.adj(v)) {
                int w = e.other(v);
                if (e.residualCapacityTo(w) > 0 && !marked[w]) {
                    edgeTo[w] = e;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
        return marked[t];
    }
    public double value() {
        return value;
    }
    public boolean intCut(int v) { //在残留网络中v->s是否可达
        return marked[v];
    }
}

参考链接

  • <算法导论>
  • <算法>(普林斯顿Algorithm II)
  • 网络流:最要命流动,最小割
    基本概念及算法
  • 顶老流动问题-Ford-Fulkerson算法

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图