P1343 地震逃生

题目描述

汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有n个点，m条边。1号点为教室，n号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从1号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，x名学生分几批才能运完。

输入格式

第一行3个整数n,m,x(x<2^31,n<=200,m<=2000)；以下m行，每行三个整数a,b,c（a1,a<>b,0描述一条边，分别代表从a点到b点有一条边，且可容纳c名学生。

输出格式两个整数，分别表示每批最多能运出多少个学生，x名学生分几批才能运完。如果无法到达目的地（n号点）则输出“Orz Ni Jinan

Saint Cow!”

输入输出样例

说明/提示【注释】

比如有图

1 2 100

2 3 1

100个学生先冲到2号点，然后1个1个慢慢沿2-3边走过去

18神牛规定这样是不可以的……

也就是说，每批学生必须同时从起点出发，并且同时到达终点

思路

Edmods_kraps / Dinic / ISAP

题解一

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = 205;

const int maxm = 2005;

struct Edge

{

    int v,w,next;

} edge[2*maxm];

int head[maxn];

int dis[maxn];      //每次bfs 都找最短路经 进行开刀

int use[maxn];

int pre[2*maxm];    //前驱数组，⚠️ pre[x] = i ,表示的意思是，到i这个节点的上一条边是 i

int min_flow[maxn];

int n, m, x;

int k = -1;

void Add(int u, int v, int w)

{

    edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;

    edge[++ k] = (Edge){ u, 0, head[v]}; head[v] = k;

}

//bfs用于分层

bool bfs(int s, int e)

{

    for(int i = 1; i <= n; i ++)

        dis[i] = INF, use[i] = 0, min_flow[i] = INF;

    dis[s] = 0;

    queue<int> q;

    q.push(s);

    int u,v;

    while(! q.empty())

    {

        u = q.front(); q.pop();

        use[u] = 0;

        for(int i = head[u]; i != -1; i = edge[i].next)

        {

            v = edge[i].v;

            if(dis[v] > dis[u] + 1 && edge[i].w)

            {

                dis[v] = dis[u] + 1;

                pre[v] = i;

                min_flow[v] = min(min_flow[u], edge[i].w);

                if(! use[v])

                {

                    q.push(v);

                    use[v] = 1;

                }

            }

        }

        if(min_flow[e] != INF)

            break;

    }

    if(min_flow[e] == INF)

        return false;

    //更新网络中的参与流量

    int now = e;

    while(now != s)

    {

        edge[pre[now]].w -= min_flow[e];

        edge[pre[now]^1].w += min_flow[e];

        now = edge[pre[now]^1].v;

    }

    return true;

}

int Edmonds_krap(int s, int e)

{

    int mx_flw = 0;

    while(bfs(s, e))

    {

        mx_flw += min_flow[e];

    }

    return mx_flw;

}

inline void init()

{

    for(int i = 0; i <= n; i ++)

        head[i] = -1;

    k = -1;

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> m >> x;

    init();

    int u, v, w;

    for(int i = 1; i <= m; i ++)

        cin >> u >> v >> w, Add(u, v, w);

    int res = Edmonds_krap(1, n);

    if(! res)

        cout << "Orz Ni Jinan Saint Cow!\n";

    else

    {

        cout << res << " ";

        int tem = x;

        tem /= res;

        if(tem * res == x)

            cout << tem << endl;

        else

            cout << tem + 1 << endl;

    }

    return 0;

}

题解一

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = 205;

const int maxm = 2005;

struct Edge

{

    int v,w,next;

} edge[2*maxm];

int head[maxn],cur[maxn];

int deep[maxn];

int n, m, x;

int k = -1;

void Add(int u, int v, int w)

{

    edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;

    edge[++ k] = (Edge){ u, 0, head[v]}; head[v] = k;

}

//bfs用于分层

bool bfs(int s, int e)

{

    for(int i = 0; i <= n; i ++)

        cur[i] = head[i], deep[i] = INF;

    deep[s] = 0;

    queue<int> q;

    q.push(s);

    int u,v;

    while(! q.empty())

    {

        u = q.front(); q.pop();

        for(int i = head[u]; i != -1; i = edge[i].next)

        {

            v = edge[i].v;

            if(edge[i].w && deep[v] == INF)

            {

                deep[v] = deep[u] + 1;

                q.push(v);

            }

        }

        if(deep[e] != INF)

            return true;

    }

    return false;

}

//dfs 用于增广网

int dfs(int now, int e, int limit)

{

    if(! limit || now == e) return limit;

    int flow = 0, f;

    for(int i = cur[now]; i != -1; i = edge[i].next)

    {

        if(deep[edge[i].v] == deep[now] + 1 && (f = dfs( edge[i].v, e, min( limit, edge[i].w))))

        {

            flow += f;          //答案把这一份合理的流量加上去

            limit -= f;         //限制条件也要改变，，这个limit 可能被一个点的多条实用。。

            edge[i].w -= f;     //正逆向边也要相应的操作

            edge[i^1].w += f;

            cur[now] = i;       //当前弧优化

            if(limit == 0)

                break;

        }

    }

    return flow;

}

int Dinic(int s, int e)

{

    int mx_flw = 0;

    while(bfs(s, e))

        mx_flw += dfs(s, e, INF);

    return mx_flw;

}

inline void init()

{

    for(int i = 0; i <= n; i ++)

        head[i] = -1;

    k = -1;

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> m >> x;

    init();

    int u, v, w;

    for(int i = 1; i <= m; i ++)

        cin >> u >> v >> w, Add(u, v, w);

    int res = Dinic(1, n);

    if(! res)

        cout << "Orz Ni Jinan Saint Cow!\n";

    else

    {

        cout << res << " ";

        int tem = x;

        tem /= res;

        if(tem * res == x)

            cout << tem << endl;

        else

            cout << tem + 1 << endl;

    }

    return 0;

}

题解一

#include<iostream>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

#define INF 1e9

const int maxn = 10005;

const int maxm = 200005;

int n, m, s, e;

int k;

struct Edge

{

    int v,w,next;

} edge[2 * maxm];

int head[maxn],cur[maxn],deep[maxn];

int last[maxm];

int num[maxm];      // num 桶，用来统计每个分层的节点的数量

void Add(int u, int v, int w)

{

    edge[++ k] = (Edge){ v, w, head[u]};

    head[u] = k;

    edge[++ k] = (Edge){ u, 0, head[v]};

    head[v] = k;

}

//bfs 用于更新deep层

void bfs(int e)

{

//    for(int i = 0; i <= n; i ++)

//        cur[i] = head[i], deep[i] = n;

    for(int i = 0; i <= m; i ++) cur[i] = head[i];

    for(int i = 1; i <= n; i ++) deep[i] = n;

    deep[e] = 0;

    queue<int> q;

    q.push(e);

    int u, v, w;

    while(! q.empty())

    {

        u = q.front(); q.pop();

        for(int i = head[u]; i != -1; i = edge[i].next)

        {

            v = edge[i].v;

            if(edge[i^1].w && deep[v] == n)      //正图 边存在 且 v这个节点没有被求过

            {

                deep[v] = deep[u] + 1;

                q.push(v);

            }

        }

    }

}

int Add_flow(int s, int e)

{

    int ans = INF;

    int now = e;

    while(now != s)

    {

        ans = min(ans, edge[last[now]].w);

        now = edge[last[now]^1].v;

    }

    now = e;

    while(now != s)

    {

        edge[last[now]].w -= ans;

        edge[last[now]^1].w += ans;

        now = edge[last[now]^1].v;

    }

    return ans;

}

int isap(int s, int e)

{

    int now = s;    //从起点开始进行操作

    bfs(e);         //先找出来一条边 被操作的增光路

    for(int i = 1; i <= n; i ++) num[deep[i]] ++;

    int mx_flw = 0;

    while(deep[s] < n)

    {

        if(now == e)        //如果到达汇点直接增广，重新回到源点进行下一轮增广

        {

            mx_flw += Add_flow(s, e);

            now = s;

        }

        bool has_find = 0;

        for(int i = cur[now]; i != -1; i = edge[i].next)

        {

            if(edge[i].w && deep[now] == deep[edge[i].v] + 1)

            {

                has_find = 1;   //做标记已经找到一种可行路径

                cur[now] = i;     //优化当前弧

                now = edge[i].v;

                last[edge[i].v] = i;

                break;

            }

        }

        if(! has_find)

        {

            int minn = n - 1;

            for(int i = head[now]; i != -1; i = edge[i].next)

                if(edge[i].w)

                    minn = min(minn, deep[edge[i].v]);

            if( (-- num[deep[now]]) == 0) break;   //gap 优化出现了断层

            num[deep[now] = minn + 1] ++;

            cur[now] = head[now];

            if(now != s)

                now = edge[last[now]^1].v;

        }

    }

    return mx_flw;

}

void init()

{

    k = -1;

    memset(head, -1, sizeof(head));

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    int st;

    cin >> n >> m >> st;

    init();

    int u,v,w;

    for(int i = 1; i <= m; i ++)

        cin >> u >> v >> w, Add(u, v, w);

    int cnt = isap(1, n);

    if(! cnt)

        cout <<"Orz Ni Jinan Saint Cow!\n";

    else

    {

        cout << cnt << " ";

        int tem = st;

        tem /= cnt;

        if(tem * cnt == st)

            cout << tem << endl;

        else

            cout << tem + 1 << endl;

    }

    return 0;

}

巴特西

P1343 地震逃生（最大流板题）

P1343 地震逃生

思路

题解一

题解一

题解一

最新文章

热门文章