洛谷P1344坏牛奶追踪问题（最小割算法应用）

作者：我就是我 | 来源：互联网 | 2024-11-07 14:50

在洛谷P1344的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。

第一问求最小割。第二问求割边最小的最小割。

我们直接求出第二问就可以求出第一问了。

对于求割边最小，如果我们可以把每条边都附加一个1的权值，那么求最小割是不是会优先选择1最少的边呢。

但是如果直接把边的权值+1，这样求得的最小割就不是原来的最小割了，那是因为1会对原来的容量产生影响。

如果把每条边的权值都乘以一个很大的常数，再加上附加权值1，这样求出的最小割是不是显然也是原图的最小割呢。

那么最终的答案除以这个常数就是最小割的容量，最终的答案模这个常数就是最小割的最小割边数。

# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include <set>
# include 
# include 
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-7
# define MOD 1024523
# define INF 1e16
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; ii)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Out(int a) {
    if(a<0) {putchar('-'); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
const int N=35;
//Code begin...

struct Edge{int p, next; LL w;}edge[4005];
int head[N], cnt=2, s, t, vis[N];
queue<int>Q;

void add_edge(int u, int v, LL w){
    edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;
    edge[cnt].p=u; edge[cnt].w=0; edge[cnt].next=head[v]; head[v]=cnt++;
}
int bfs(){
    int i, v;
    mem(vis,-1);
    vis[s]=0; Q.push(s);
    while (!Q.empty()) {
        v=Q.front(); Q.pop();
        for (i=head[v]; i; i=edge[i].next) {
            if (edge[i].w>0 && vis[edge[i].p]==-1) {
                vis[edge[i].p]=vis[v] + 1;
                Q.push(edge[i].p);
            }
        }
    }
    return vis[t]!=-1;
}
LL dfs(int x, LL low){
    int i;
    LL a, temp=low;
    if (x==t) return low;
    for (i=head[x]; i; i=edge[i].next) {
        if (edge[i].w>0 && vis[edge[i].p]==vis[x]+1){
            a=dfs(edge[i].p,min(edge[i].w,temp));
            temp-=a; edge[i].w-=a; edge[i^1].w += a;
            if (temp==0) break;
        }
    }
    if (temp==low) vis[x]=-1;
    return low-temp;
}
int main ()
{
    int n, m, u, v, w;
    LL P=10000000;
    scanf("%d%d",&n,&m); s=1; t=n;
    FOR(i,1,m) scanf("%d%d%d",&u,&v,&w), add_edge(u,v,(LL)w*P+1);
    LL sum=0;
    while (bfs()) sum+=dfs(s,INF);
    printf("%lld %lld\n",sum/P,sum%P);
    return 0;
}

View Code

推荐阅读

js
P3796 AC自动机强化版题解 - Aho-Corasick Algorithm

本文提供了一个关于AC自动机（Aho-Corasick Algorithm）的详细解析与实现方法，特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念，还重点讲解了如何通过构建失败指针（fail pointer）来提高字符串匹配效率。 ... [详细]

蜡笔小新 2024-11-23 13:17:52
js
HihoCoder1398：最大权闭合子图问题解析

本文详细探讨了HihoCoder平台上的1398号问题——最大权闭合子图的求解方法。通过具体实例，深入分析了最大权闭合子图的概念及其算法实现。 ... [详细]

蜡笔小新 2024-11-23 09:31:29
js
网络流24题——试题库问题

题目描述：假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]

蜡笔小新 2024-11-22 11:33:55
byte
物联网学习之旅：微信小程序控制STM32（三）STM32代码编写

STM32代码编写STM32端不需要写关于连接MQTT服务器的代码，连接的工作交给ESP8266来做，STM32只需要通过串口接收和发送数据，间接的与服务器交互。串口三配置串口一已 ... [详细]

蜡笔小新 2024-11-23 21:37:55
blob
【MySQL】frm文件解析

官网说明：http:dev.mysql.comdocinternalsenfrm-file-format.htmlfrm是MySQL表结构定义文件，通常frm文件是不会损坏的，但是如果 ... [详细]

蜡笔小新 2024-11-23 10:29:06
char
编程解析：CF989C 花朵之雾 (构造算法)

本文深入探讨了CF989C '花朵之雾'问题的构造算法，提供了详细的解题思路和代码实现。 ... [详细]

蜡笔小新 2024-11-23 09:59:40
char
摊还算法——贡献转移

贡献转移在计算每个元素的作用的时候，我们可以通过反向枚举作用效果，添加到作用元素的身上，这种方法叫做贡献转移。更正式的说， ... [详细]

蜡笔小新 2024-11-22 19:41:13
char
深入Luat OS：C与Lua混合编程指南

本文详细介绍了在Luat OS中如何实现C与Lua的混合编程，包括在C环境中运行Lua脚本、封装可被Lua调用的C语言库，以及C与Lua之间的数据交互方法。 ... [详细]

蜡笔小新 2024-11-22 15:52:23
char
阶段一：Hankson的趣味数学挑战——不使用辗转相除法求解特定条件下的正整数

Hanks博士是一位著名的生物技术专家，他的儿子Hankson对数学有着浓厚的兴趣。最近，Hankson遇到了一个有趣的数学问题，涉及求解特定条件下的正整数x，而不使用传统的辗转相除法。 ... [详细]

蜡笔小新 2024-11-22 14:26:49
post
hlg_oj_1116_选美大赛

hlg_oj_1116_选美大赛这题是最长子序列，然后再求出路径就可以了。开始写的比较乱，用数组什么的，后来用了指针就好办了。现在把代码贴 ... [详细]

蜡笔小新 2024-11-22 09:20:30
js
深入解析Apache Mina开发指南

本文由chszs撰写，详细介绍了Apache Mina框架的核心开发流程及自定义协议处理方法。文章涵盖从创建IoService实例到协议编解码的具体步骤，适合希望深入了解Mina框架应用的开发者。 ... [详细]

蜡笔小新 2024-11-23 15:02:21
js
HDU 1042 N! 题解与代码实现

本文针对HDU 1042 N! 问题提供详细的解析和代码实现。题目要求计算给定整数N（0 ≤ N ≤ 10000）的阶乘N!。文章不仅提供了算法思路，还附上了C++语言的具体实现。 ... [详细]

蜡笔小新 2024-11-23 14:30:12
js
LeetCode 102 - 二叉树层次遍历详解

本文详细解析了LeetCode第102题——二叉树的层次遍历问题，提供了C++语言的实现代码，并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]

蜡笔小新 2024-11-23 12:14:28
byte
java 编码与基础数据类型

编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]

蜡笔小新 2024-11-23 09:24:18
byte
解决iOS应用推送通知错误：未找到有效aps-environment权限

在尝试加载支持推送通知的iOS应用程序的Ad Hoc构建时，遇到了‘no valid aps-environment entitlement found for application’的错误提示。本文将探讨此错误的原因及多种可能的解决方案。 ... [详细]

蜡笔小新 2024-11-21 19:26:31

我就是我

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章