首页 > 其他分享 >最小割

最小割

时间:2024-08-20 22:54:14浏览次数:12  
标签:int cap flow 最小 edges leq Edge

题目描述
给定\(n\)个点\(m\)条边的有向图,删掉第\(i\)条边的代价为\(c[i]\)。

请删掉代价之和最少的边,使得从\(1\)号点出发到达不了\(n\)号点。
输入
第一行包含一个正整数\(T(1\leq T\leq 10)\),表示测试数据的组数。

每组数据第一行包含两个正整数\(n,m(1\leq n\leq 50,1\leq m\leq 1000)\)。

接下来\(m\)行,每行三个正整数\(a[i],b[i],c[i](1\leq a[i],b[i]\leq n,a[i]\neq b[i],1\leq c[i]\leq 10000)\),表示一条起点是\(a[i]\),终点是\(b[i]\)的边,删掉它的代价是\(c[i]\)。
输出
对于每组数据输出一行一个整数,即最小代价。

#include<bits/stdc++.h>
using namespace std;
typedef vector<string> VS;
const int N = 110,INF = 1e9;
struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

bool operator < (const Edge& a, const Edge& b) {
  return a.from < b.from || (a.from == b.from && a.to < b.to);
}

struct ISAP {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[N];
  bool vis[N];
  int d[N],cur[N],p[N],num[N];

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t] = 1;
    d[t] = 0;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = 1;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }

  void init(int n) {
    this->n = n;
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  int Augment() {
    int x = t, a = INF;
    while (x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap - e.flow);
      x = edges[p[x]].from;
    }
    x = t;
    while (x != s) {
      edges[p[x]].flow += a;
      edges[p[x] ^ 1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof(num));
    for (int i = 0; i < n; i++) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while (d[s] < n) {
      if (x == t) {
        flow += Augment();
        x = s;
      }
      int ok = 0;
      for (int i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (e.cap > e.flow && d[x] == d[e.to] + 1) {
          ok = 1;
          p[e.to] = G[x][i];
          cur[x] = i;
          x = e.to;
          break;
        }
      }
      if (!ok) {
        int m = n - 1;
        for (int i = 0; i < G[x].size(); i++) {
          Edge& e = edges[G[x][i]];
          if (e.cap > e.flow) m = min(m, d[e.to]);
        }
        if (--num[d[x]] == 0) break;
        num[d[x] = m + 1]++;
        cur[x] = 0;
        if (x != s) x = edges[p[x]].from;
      }
    }
    return flow;
  }
};
ISAP FG;
void solve()
{
	int n,m;
	cin>>n>>m;
	//最小割的源点和汇点直接选用图里的点即可
	int s = 1,t = n;
	FG.init(n+1);
	
	for(int i=0;i<m;++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		FG.AddEdge(u,v,w);
	}
	cout<<FG.Maxflow(s,t)<<'\n';
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:int,cap,flow,最小,edges,leq,Edge
From: https://www.cnblogs.com/ruoye123456/p/18370516

相关文章

  • C++图笔记(三)有向无环图(及最小生成树(略))以及剩下的排序
    目录一,定义:1,有向无环图 2,拓朴排序 1,每个顶点出现且仅仅出现一次。 2,若存在一条从顶点A到顶点B的路径,那么在序列中顶点A出现在顶点B的前面。二,DAG的性质性质1.  从任意一个起点进行dfs,必不会陷入死循环。性质2.  入度为0的点信息确定,删掉入度为0的点......
  • 【代码随想录训练营第42期 Day32打卡 - 从零开始动态规划 - LeetCode 509. 斐波那契数
    目录一、做题心得二、动规五步走三、题目与题解题目一:509.斐波那契数题目链接题解1:记忆性递归 题解2:动态规划题目二:70.爬楼梯 题目链接题解:动态规划题目三:746.使用最小花费爬楼梯题目链接题解:动态规划三、小结一、做题心得今天开始动态规划章节的第一......
  • 【数据结构与算法】如何构建最小堆
    最小堆的定义最小堆,作为一种独特且重要的数据结构,它是一种特殊的二叉树。在这种二叉树中,有一个关键的规则:每一个父节点所存储的值,都必然小于或者等于其对应的子节点的值。这一规则确保了根节点总是承载着整个堆中的最小数值。例如,下面这样一个简单的结构就是最小堆:1......
  • 【C++二分查找】1954. 收集足够苹果的最小花园周长
    本文涉及的基础知识点C++二分查找LeetCode1954.收集足够苹果的最小花园周长给你一个用无限二维网格表示的花园,每一个整数坐标处都有一棵苹果树。整数坐标(i,j)处的苹果树有|i|+|j|个苹果。你将会买下正中心坐标是(0,0)的一块正方形土地,且每条边都与两条坐......
  • 二叉树——14.二叉搜索树的最小绝对差
    力扣题目链接给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。解题思路总结中序遍历是一种有效的方法,可以将二叉搜索树节点的值按从小到大的顺序排列。通过将这些值存入一个有序数组后,只需遍历数组,比较相邻元素的差值,即可找到树中任意两......
  • 2024-08-17:用go语言,给定一个从0开始的整数数组nums和一个整数k, 每次操作可以删除数组
    2024-08-17:用go语言,给定一个从0开始的整数数组nums和一个整数k,每次操作可以删除数组中的最小元素。你的目标是通过这些操作,使得数组中的所有元素都大于或等于k。请计算出实现这个目标所需的最少操作次数。输入:nums=[2,11,10,1,3],k=10。输出:3。解释:第一次操作后,nums变......
  • OpenCV图像处理——按最小外接矩形剪切图像
    引言在图像处理过程中,提取感兴趣区域(ROI)并在其上进行处理后,往往需要将处理后的结果映射回原图像。这一步通常涉及以下几个步骤:找到最小外接矩形:使用cv::boundingRect或cv::minAreaRect提取感兴趣区域的最小外接矩形。从原图中提取ROI:根据矩形坐标从原图中剪切出RO......
  • 代码随想录day32 || 509 斐波那契数列,70 爬楼梯,746 最小代价爬楼梯
    509斐波那契数列funcfib(nint)int{ //dp五部曲 //1dp数组含义以及下标含义:本题保存的是完整的斐波那契数列,i对应数列的第i个数字 //2递推公式:F(n)=F(n-1)+F(n-2) //3dp数组初始化:由递推公式推到,0,1两位需要手动赋值,否则,oor //4遍历顺序:求......
  • C语言-使用数组法,指针法实现将一个5X5的矩阵中最大的元素放在中心,四个角分别放四个最
    1.题目要求:将一个5X5的矩阵中最大的元素放在中心·,四个角分别放四个最小的元素(顺序为从左到右,从上到下,从小到大存放),写一函数实现之。2.数组法实现#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>//一、数组法实现intmain(){ intarr[5][5]={ {1,2,3,4,5},......
  • python 计算中位数、四分位数、最大值、最小值等
    还是之前的那一堆csv数,主要算每列的中位数、四分位数、最大值、最小值等我在这里做个笔记,方便下次用的时候直接粘过来用#!usr/bin/envpython#-*-coding:utf-8-*-"""@author:Suyue@file:vilolinpic.py@time:2024/08/13@desc:"""importpandasaspddf=pd.rea......