首页 > 其他分享 >代码临时存放

代码临时存放

时间:2023-11-30 11:23:35浏览次数:31  
标签:pre slack 临时 代码 ey ex delta 存放 ll

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 505;
const ll inf = 1e18;

ll n, m, mp[N][N], matched[N];
ll slack[N], pre[N], ex[N], ey[N];//ex,ey顶标
bool visx[N], visy[N];

void match(ll u){
    ll x, y = 0, yy = 0, delta;
    memset(pre, 0, sizeof(pre));
    for(ll i = 1; i <= n; i++) slack[i] = inf;
    matched[y] = u;
    while(1){
        x = matched[y]; delta = inf; visy[y] = 1;
        for(ll i = 1; i <= n; i++){
            if(visy[i]) continue;
            if(slack[i] > ex[x]+ey[i]-mp[x][i]){
                slack[i] = ex[x]+ey[i]-mp[x][i];
                pre[i] = y;
            }
            if(slack[i] < delta){delta = slack[i]; yy = i;}
        }
        for(ll i = 0; i <= n; i++){
            if(visy[i]) ex[matched[i]] -= delta, ey[i] += delta;
            else slack[i] -= delta;
        }
        y = yy;
        if(matched[y] == -1) break;
    }
    while(y){ matched[y] = matched[pre[y]]; y = pre[y];}
}

ll KM(){
    memset(matched, -1, sizeof(matched));
    memset(ex, 0, sizeof(ex));
    memset(ey, 0, sizeof(ey));
    for(ll i = 1; i <= n; i++){
        memset(visy, 0, sizeof(visy));
        match(i);
    }
    ll res = 0;
    for(ll i = 1; i <= n; i++)
        if(matched[i] != -1) res += mp[matched[i]][i];
    return res;
}

int main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            mp[i][j] = -inf;
    for(ll i = 1; i <= m; i++){
        ll u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        mp[u][v] = w;
    }
    printf("%lld\n", KM());
    for(ll i = 1; i <= n; i++)
        printf("%lld ", matched[i]);
    printf("\n");
    return 0;
}

标签:pre,slack,临时,代码,ey,ex,delta,存放,ll
From: https://www.cnblogs.com/meteor2008/p/17866882.html

相关文章

  • 零代码集成自动化的实现逻辑是什么?
    零代码的概念是什么?零代码平台是一种软件开发工具或平台,非技术人员能够创建和部署应用程序,而无需编写任何代码。它提供了可视化的界面和拖拽式的操作,使用户能够通过简单的配置和组合,以图形化的方式构建应用程序。这种平台通常包含了丰富的预定义组件、模板和工具,用户可以根据自己......
  • 如何编写优雅的异步代码 — CompletableFuture
    如何编写优雅的异步代码—CompletableFuture Java实现异步编程的8种方式  ......
  • java代码连接redis
    RedisURIuri=RedisURI.Builder.redis("XXXX",16379).withDatabase(6).withPassword("XXXX").build();redisClient=RedisClient.create(uri);conn......
  • 一行代码解决IE停用后无法继续使用IE弹窗功能的问题
    微软在2023年2月14日通过Edge浏览器更新,彻底封死IE。WindowsUpdate中没有记录、开始菜单中的IE以及桌面IE图标双击自动打开Edge,默认程序设置了IE也没有任何效果,仅能通过Edge浏览器设置IE模式浏览。但是之前通过这种方式使用IE最近发现无法弹窗了,而有些IE应用要求必须弹窗,在网上尝......
  • 解决VS编译C++时,该文件包含不能在当前代码页(936)中表示的字符。请将该文件保存为 Uni
    使用VS编译C++时,报错: warningC4819:该文件包含不能在当前代码页(936)中表示的字符。请将该文件保存为Unicode格式以防止数据丢失。利用VS的高级保存选项,修改合适的编码规则即可解决,最新版VS需要手动添加高级保存选线的命令,方法如下:打开工具-->自定义 选择命令-->选择添......
  • 代码审计
    代码审计代码审计bugku源代码根据提示先看源代码,如下:​​‍​​‍是escape加密,放到在线网站解密即可。得到一串代码:varp1='functioncheckSubmit(){vara=document.getElementById("password");if("undefined"!=typeofa){if("67d709b2b';varp2='aa648cf......
  • 代码大全2 读后感1
    《代码大全2》是由美国软件工程师SteveMcConnell所著的一本软件开发经典著作。这本书的全名是《CodeComplete2:APracticalHandbookofSoftwareConstruction》。第一版于1993年出版,而第二版则于2004年问世。以下是《代码大全2》的主要内容和特点:1.全面的软件构建指南:《代......
  • 图像倾斜校正算法的MATLAB实现:图像倾斜角检测及校正|附代码数据
    原文链接:http://tecdat.cn/?p=13981 原文出处:拓端数据部落公众号 随着多媒体技术的不断发展,数码相机,高清拍照手机等多媒体设备己经在人们的生活中占据了越来越重要的地位。 通过采用图像处理技术,可以将数码设备采集到的文字、图片等信息转化成其他信息形势输出,例如转......
  • 聪明方法学python task5 条件/代码风格
    条件控制elif代替了C语言中的elseif缩进划分代码块嵌套if仍然成立多返回语句defabs(n):  ifn<0:    return-n  returnn match-case类比switch-case语句_可以匹配一切。deftest(a):​•matcha:​•case1:​•......
  • 优雅代码
    优雅代码part1写注释方便自己看,也方便别人阅读tab键相当于4空格换行与缩进换行符\导入规范假设目录:Tree|___m1.py|___m2.py|___Branch |___m3.py |___m4,py在m2.py写代码defprintself(): print("m2")在m3.py写代码defprintself(): print("m3")import本地......