1423. 魔王bug的2色定理

2024-03-06 09:08
文章标签 bug 定理 1423 魔王

本文主要是介绍1423. 魔王bug的2色定理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转换为求最小割

#include<iostream>

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using  namespace std;
const int INF = 10000000;
vector<int> path[220];
int cap[220][220];
int flow[220][220];
int a[220];
int p[220];
int n,m;
void solve(){
int s = 0;
int t = n+1;
  int ans = 0;


  queue<int> q;
  memset(flow, 0, sizeof(flow));
  for(;;) {
    memset(a, 0, sizeof(a));
    a[s] = INF;
    q.push(s);
    while(!q.empty()) {
      int u = q.front(); q.pop();
 for(int i = 0; i<path[u].size(); i++) if(!a[path[u][i]] && cap[u][path[u][i]]>flow[u][path[u][i]]){
        p[path[u][i]] = u; q.push(path[u][i]);
        a[path[u][i]] = a[u] < cap[u][path[u][i]]-flow[u][path[u][i]]?a[u]:cap[u][path[u][i]]-flow[u][path[u][i]];
      }
    }
    if(a[t] == 0) break;
    for(int u = t; u != s; u = p[u]) {
      flow[p[u]][u] += a[t];
      flow[u][p[u]] -= a[t];
    }
    ans += a[t];
  }


  printf("%d\n", ans);
  ///return 0;


}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 0;i<=n+1;i++)path[i].clear();
memset(cap,0,sizeof(cap));
int a,b;
for(int i = 0;i<m;i++){
scanf("%d%d",&a,&b);
path[a].push_back(b);
path[b].push_back(a);
cap[a][b] = cap[b][a] = 1;
}
scanf("%d",&a);
for(int i = 0;i<a;i++){
scanf("%d",&b);
path[0].push_back(b);
path[b].push_back(0);
cap[0][b] = INF;
}
scanf("%d",&a);
for(int i = 0;i<a;i++){
scanf("%d",&b);
path[n+1].push_back(b);
cap[b][n+1] = INF;
path[b].push_back(n+1);
}
solve();

}
return 0;
}

这篇关于1423. 魔王bug的2色定理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/779528

相关文章

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

Java验证辛钦大数定理

本实验通过程序模拟采集大量的样本数据来验证辛钦大数定理。   实验环境: 本实验采用Java语言编程,开发环境为Eclipse,图像生成使用JFreeChart类。   一,验证辛钦大数定理 由辛钦大数定理描述为: 辛钦大数定理(弱大数定理)  设随机变量序列 X1, X2, … 相互独立,服从同一分布,具有数学期望E(Xi) = μ, i = 1, 2, …, 则对于任意正数ε ,

CPC23三 K.(Lucas定理)

K.喵喵的神·数 Time Limit: 1 Sec Memory Limit: 128 MB Description 喵喵对组合数比较感兴趣,并且对计算组合数非常在行。同时为了追求有后宫的素质的生活,喵喵每天都要研究质数。 我们先来复习一下什么叫做组合数。对于正整数P、T 然后我们再来复习一下什么叫质数。质数就是素数,如果说正整数N的约数只有1和它本身,N

JavaBug系列-解决SpringBoot返回Xml结构的问题

JavaBug系列之SpringBoot返回Xml结构的问题 Java医生一、关于错误信息二、如何解决问题 Java医生 本系列记录常见Bug,以及诊断过程和原因 作者:Java医生 教学: Java企业项目辅导,专注于辅导新入职员工,解决各种问题! V:study_51ctofx 一、关于错误信息 如图,SpringBoot请求返回Xml格式信息 通过以上信息分析,

JavaBug系列- Failed to load driver class com.mysql.cj.jdbc.Driver in either of HikariConfig class load

JavaBug系列之Mysql驱动问题 Java医生一、关于错误信息二、如何解决问题 Java医生 本系列记录常见Bug,以及诊断过程和原因 Java/一对一零基础辅导/企业项目一对一辅导/日常Bug解决/代码讲解/毕业设计等 V:study_51ctofx 一、关于错误信息 APPLICATION FAILED TO START Description: Fai

【解决bug之路】npm install node-sass(^4.14.1)连环报错解决!!!(Windows)

有关node-sass的深入分析可参考:又报gyp ERR!为什么有那么多人被node-sass 坑过? 主要有如下三方面错误,请自查: 1.node,npm版本需与node-sass版本匹配,像node-sass(^4.14.1)就得node 14.x版本才可以,node 16不行 gyp ERR! build error15 gyp ERR! stack Error: `

排查 MyBatis XML 配置中的 IF 语句与传值名称不匹配的 Bug

文章目录 本文档只是为了留档方便以后工作运维,或者给同事分享文档内容比较简陋命令也不是特别全,不适合小白观看,如有不懂可以私信,上班期间都是在得 前言,在改一个bug得时候发现一个有意思得问题,就是mybatis得xml中if判断得问题,传值名字不匹配依旧可以进行判断,如下图 传值userName,但是有意思得事情出现了,进了if,并且没有报错,尝试了两次都是这

彻底解决魅族手机无法彻底卸载应用的bug

使用Flyme系统的同学可能会遇到一个问题: 卸载了某些软件(例如通过开发者模式调试安装的应用)后,实际这个应用还残留在系统,当你用低版本或者其他签名的apk覆盖安装的时候会提示“安装失败”,要求你卸载后重新安装。 可是无论你从应用列表寻找还是清理垃圾,都根本找不到这个应用。 闹鬼?这个bug一直伴随着flyme,可怜工程师们竟然一个都没发现。 今天笔者教大家一招解决这个问题。

今天做了freemaker 导出word文档 的bug修复,解决 \n换行 问题

结合Freemaker导出文件 public void exportSimpleWord() throws Exception{// 要填充的数据, 注意map的key要和word中${xxx}的xxx一致Map<String,String> dataMap = new HashMap<String,String>();dataMap.put("username", "张三");dataMap.

量化交易面试:什么是中心极限定理?

中心极限定理(Central Limit Theorem, CLT)是概率论和统计学中的一个重要定理,它描述了在一定条件下,独立随机变量的和的分布趋向于正态分布的性质。这个定理在量化交易和金融分析中具有重要的应用价值。以下是对中心极限定理的详细解释: 基本概念: 中心极限定理指出,当我们从一个具有任意分布的总体中抽取足够大的样本时,样本均值的分布将近似于正态分布,无论原始总体的分布是什么样的。