专栏首页饶文津的专栏【POJ 1273】Drainage Ditches(网络流)

【POJ 1273】Drainage Ditches(网络流)

一直不明白为什么我的耗时几百毫秒,明明差不多的程序啊,我改来改去还是几百毫秒。 ...一个小时后:明白了,原来把最大值0x3f(77)取0x3f3f3f3f就把时间缩短为16ms了。可是为什么原来那样没有WA呢?哦,明白了,因为最大值写小了,dicnic会多跑几遍。 嗯顺便:0x3f3f3f3f也就是1061109567,也就是10^9级别的,是一个很大的数,而且加上一个10^9级别以下的数字也不会溢出。所以很多时候最大值取这个会比较好。最大的int是0x7fffffff,可以用常量INT_MAX 代替。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int arc[201][201], d[201], q[201];
int m, n, ans,tans;
bool bfs()
{
    memset(d, -1, sizeof d);
    queue<int>q;
    q.push(1);
    d[1] = 0;
    while(!q.empty())
    {
        int i,k=q.front();
        q.pop();
        for(i = 1; i <= n; i++)
            if(arc[k][i] > 0 && d[i] == -1)
            {
                d[i] = d[k] + 1;
                q.push(i);
            }
    }
    return d[n]>0;
}
int dinic (int k, int low)
{
    if(k == n)return low;
    int a,i;
    for(i = 1; i <= n; i++)
        if(d[i] == d[k] + 1&&  arc[k][i] > 0 &&(a = dinic(i, min(low, arc[k][i]))))
        {
                arc[k][i] -= a;
                arc[i][k] += a;
                return a;
        }
    return 0;
}
int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        memset(arc, 0, sizeof arc);
        for(int i = 0; i < m; i++)
        {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            arc[u][v] += c;
        }
        ans = 0;
        while(bfs())
            while(tans=dinic(1, 0X3f3f3f3f)) ans += tans;
        printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • 【AtCoder078D】Fennec VS. Snuke

    AtCoder Regular Contest 078 D - Fennec VS. Snuke

    饶文津
  • 【HDU 5833】Zhu and 772002(异或方程组高斯消元)

    比如12=2^2*3,对应的奇偶值为01(2的个数是偶数为0,3的个数是奇数为1),3的对应奇偶值为01,于是12*3是完全平方数。

    饶文津
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 挑战程序竞赛系列(31):4.5剪枝

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty
  • Remove Duplicates from Sorted Array

    问题:将有序的数组中重复的数字去掉 分析:由于有序所以只用和前一个比较就行 class Solution { public: int removeDup...

    用户1624346
  • C++二分图代码实现

    #include <iostream> #include <cstdio> #include <vector> using namespace std; #d...

    kalifa_lau
  • 2014年第五届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • 快乐AC三道题---第一周

    我们要解决的无非是是否把下一个元素加入,是否开始维护一个新的子段。我们开一个数组b[] , 记录b[i],表示以a[i]结尾的全部子段中 最大的那个的 和。 这...

    用户7727433

扫码关注云+社区

领取腾讯云代金券