试题 算法训练 网络流裸题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了试题 算法训练 网络流裸题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1443字，纯文字阅读大概需要3分钟。

内容图文

试题 算法训练 网络流裸题

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　一个有向图，求1到N的最大流
输入格式
　　第一行N M，表示点数与边数
　　接下来M行每行s t c表示一条从s到t的容量为c的边
输出格式
　　一个数最大流量
样例输入
6 10
1 2 4
1 3 8
2 3 4
2 4 4
2 5 1
3 4 2
3 5 2
4 6 7
5 4 6
5 6 3
样例输出
8

数据约定：
n<=1000 m<=10000

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define ll long long

const int INF = 0x3f3f3f3f;
const int maxn = 200000;
#define MAXN 200000


int n, m, s, t; // s是源点，t是汇点
bool vis[MAXN];
struct Edge
{
    int to,next;
    ll w;
}edges[maxn];
ll last[maxn],flow[maxn];


int head[maxn],cnt = 1;
inline void add(int from,int to,ll w)
{
    edges[++cnt].w = w;
    edges[cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt;
}
inline ll bfs()
{
    memset(last,-1,sizeof(last));
    queue<int> q;
    q.push(s);
    flow[s] = INF;
    while(!q.empty())
    {
        int p = q.front();
        q.pop();
        if(p==t) break;
        for(int eg=head[p]; eg; eg=edges[eg].next)
        {
            int to = edges[eg].to;
            ll vol = edges[eg].w;
            if(vol>0 && last[to]==-1)
            {
                last[to] = eg;
                flow[to] = min(flow[p],vol);
                q.push(to);
            }
        }
    }
    return last[t] != -1;
}
inline ll EK()
{
    ll maxflow = 0;
    while(bfs())
    {
        maxflow += flow[t];
        for(int i=t; i!=s; i=edges[last[i]^1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i]^1].w += flow[t];
        }
    }
    return maxflow;
}
int main(){

    cin>>n>>m;
    s= 1; t = n;

    for(int i=1; i<=m; ++i){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    cout<<EK()<<endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的试题 算法训练 网络流裸题全部内容，希望文章能够帮你解决试题 算法训练 网络流裸题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---