文档章节

HDU 6346 整数规划 二分图匹配最优解

o
 osc_4nmshwhm
发布于 2018/08/07 13:30
字数 452
阅读 4
收藏 0

精选30+云产品,助力企业轻松上云!>>>

整数规划

原来的km+hunger跑法T了, 拿了一个新的板子, 新的写法是将这原来的找新的最小的d放在了上一次的残留图上,从而减小复杂度, 但是个人还不是很理解为什么最小的d下一次出现的位置一定是这次出现的位置的对应的x的点。

 

复杂度:n^3

代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 const int inf = 0x3f3f3f3f;
 5 const LL INF = 0x3f3f3f3f3f3f3f3f;
 6 const int N = 210;
 7 int val[N][N];
 8 LL lx[N],ly[N];
 9 int linky[N];
10 LL pre[N];
11 bool vis[N];
12 bool visx[N],visy[N];
13 LL slack[N];
14 int n;
15 void bfs(int k){
16     LL px, py = 0,yy = 0, d;
17     memset(pre, 0, sizeof(LL) * (n+2));
18     memset(slack, inf, sizeof(LL) * (n+2));
19     linky[py]=k;
20     do{
21         px = linky[py],d = INF, vis[py] = 1;
22         for(int i = 1; i <= n; i++)
23             if(!vis[i]){
24                 if(slack[i] > lx[px] + ly[i] - val[px][i])
25                     slack[i] = lx[px] + ly[i] -val[px][i], pre[i]=py;
26                 if(slack[i]<d) d=slack[i],yy=i;
27             }
28         for(int i = 0; i <= n; i++)
29             if(vis[i]) lx[linky[i]] -= d, ly[i] += d;
30             else slack[i] -= d;
31         py = yy;
32     }while(linky[py]);
33     while(py) linky[py] = linky[pre[py]] , py=pre[py];
34 }
35 void KM(){
36     memset(lx, 0, sizeof(int)*(n+2));
37     memset(ly, 0, sizeof(int)*(n+2));
38     memset(linky, 0, sizeof(int)*(n+2));
39     for(int i = 1; i <= n; i++)
40         memset(vis, 0, sizeof(bool)*(n+2)), bfs(i);
41 }
42 int main(){
43     int T;
44     scanf("%d", &T);
45     for(int _i = 1; _i <= T; _i++){
46         scanf("%d", &n);
47         for(int i = 1; i <= n; i++){
48             for(int j = 1; j <= n; j++){
49                 scanf("%d", &val[i][j]);
50                 val[i][j] = -val[i][j];
51             }
52         }
53         KM();
54         LL ans = 0;
55         for(int i = 1; i <= n; ++i)
56             ans += lx[i] + ly[i];
57         printf("Case #%d: %I64d\n", _i, -ans);
58     }
59     return 0;
60 }
View Code

 

 

下一篇: ps命令
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

聚焦餐饮行业,研究院昨发布数据显示

谈话,聚焦餐饮行业,研究院昨发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元.随着餐饮行业的快速发展,"如何留人"也成为餐饮企业的思考题. 记者了解到,中国饭店协会...

点击fojewio
49分钟前
20
0
3·15晚会曝光上海氪信、招财旺旺SDK包泄露隐私 后台上传交易验证码敏感信息

来源 | 央视 7月16日,央视3·15晚会曝光国美易卡、美的空调遥控器、姨妈日历、银码头等50多款软件中内嵌的SDK包读取、上传用户隐私问题。上海氪信信息技术有限公司、北京招财旺旺信息技术有...

镭射财经
58分钟前
14
0
名称=''的无效表单控件不可聚焦 - An invalid form control with name='' is not focusable

问题: I have an acute problem on my website. 我的网站上有一个严重的问题。 In Google Chrome some customers are not able to proceed to my payment page. 在Google Chrome浏览器中,某......

技术盛宴
59分钟前
14
0
Hacker News 简讯 2020-07-17

更新时间: 2020-07-17 01:01 Let’s avoid talk of ‘chemical imbalance’: it’s people in distress - (psyche.co) 让我们避免谈论“化学失衡”:这是处于困境中的人们 得分:260 | 评论:...

FalconChen
今天
92
0
【LeetCode】 59 在排序数组中查找元素的第一个和最后一个位置

题目: 解题思路: 二分法 https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/ 代......

JaneRoad
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部