Cyclic Tour (最优二分匹配)

2023-11-08 11:38
文章标签 二分 匹配 最优 tour cyclic

本文主要是介绍Cyclic Tour (最优二分匹配),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1853

题目大意:找几个环,保证环之间无公共点,并且保证找到的环权值最大;

题目思路:如果要保证图有环,并且环之间没有交点的话,那么必然每个点的出度和入度都应为1,因此我们可以把一个点拆成两个点,分别表示出度及入度,然后去找拆点后构成的二分图的完美匹配。也可以用网络流来做

题目:


Cyclic Tour

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/65535K (Java/Other)
Total Submission(s) : 5   Accepted Submission(s) : 2
Problem Description
There are N cities in our country, and M one-way roads connecting them. Now Little Tom wants to make several cyclic tours, which satisfy that, each cycle contain at least two cities, and each city belongs to one cycle exactly. Tom wants the total length of all the tours minimum, but he is too lazy to calculate. Can you help him?

Input
There are several test cases in the input. You should process to the end of file (EOF).
The first line of each test case contains two integers N (N ≤ 100) and M, indicating the number of cities and the number of roads. The M lines followed, each of them contains three numbers A, B, and C, indicating that there is a road from city A to city B, whose length is C. (1 ≤ A,B ≤ N, A ≠ B, 1 ≤ C ≤ 1000).

Output
Output one number for each test case, indicating the minimum length of all the tours. If there are no such tours, output -1.

Sample Input
  
6 9 1 2 5 2 3 5 3 1 10 3 4 12 4 1 8 4 6 11 5 4 7 5 6 9 6 5 4 6 5 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1

Sample Output
 
42 -1

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int MAXN=5000;
const int INF=0xfffffff;
int nx, ny, w[MAXN][MAXN], lx[MAXN], ly[MAXN];
int fx[MAXN], fy[MAXN], matx[MAXN], maty[MAXN];
char map[MAXN][MAXN];
int n,m;
struct node
{int x;int y;
} h[MAXN],man[MAXN];
int path(int u)
{fx[u] = 1;for (int v = 1; v <= ny; v++)if (lx[u] + ly[v] == w[u][v] && fy[v] < 0){fy[v] = 1;if (maty[v] < 0 || path(maty[v])){matx[u] = v;maty[v] = u;return 1;}}return 0;
}
void km()
{int i,j,k,ret = 0;memset(ly, 0, sizeof(ly));for (i = 1; i <= nx; i++){lx[i] = -INF;for (j = 1; j <= ny; j++)if (w[i][j] > lx[i]) lx[i] = w[i][j];}memset(matx, -1, sizeof(matx));memset(maty, -1, sizeof(maty));for (i = 1; i <= nx; i++){memset(fx, -1, sizeof(fx));memset(fy, -1, sizeof(fy));if (!path(i)){i--;int p = INF;for (k = 1; k <= nx; k++){if (fx[k] > 0)for (j = 1; j <= ny; j++)if (fy[j] < 0 && lx[k] + ly[j] - w[k][j] < p)p=lx[k]+ly[j]-w[k][j];}for (j = 1; j <= ny; j++)ly[j] += fy[j]<0 ? 0 : p;for (j = 1; j <= nx; j++)lx[j] -= fx[j]<0 ? 0 : p;}}/*for (i = 1; i <= ny; i++)ret += w[maty[i]][i];return ret;*/
}
void init()
{int a,b,c;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){w[i][j]=-INF;}}for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);if(-c>w[a][b])w[a][b]=-c;}
}
int main()
{while(scanf("%d %d",&n,&m)!=EOF){init();nx=n;ny=n;km();bool flag=false;int ans=0;for(int i=1;i<=ny;i++){if(maty[i]==-1||w[maty[i]][i]==-INF){flag=true;break;}ans+=w[maty[i]][i];}if(!flag)printf("%d\n",-ans);else printf("-1\n");}return 0;
}



这篇关于Cyclic Tour (最优二分匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que