Uva – 11383 – Golden Tiger Claw

Uva – 11383 – Golden Tiger Claw

题意:一个N*N的矩阵,第i行第j列的元素大小为w[i][j],每行求一个数row[i],每列求一个数col[j],使得row[i] + col[j] >= w[i][j],且所有的row[]与所有的col[]和总和最小( N <= 500, 其它输入数为正整数且 <= 100)。

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2378

——>>row[i] + col[j] >= w[i][j],这个恰恰是二分图最佳完美匹配的一个式子,所以,以行row为X结点,以列col为Y结点,权值即为对应元素w[i][j]的值建图,跑一次KM就好。

另外发现:用scanf(“%d”, &N) == 1比用~scanf(“%d”, &N)快了3ms。。。

 

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 500 + 10;
const int INF = 0x3f3f3f3f;

int N, w[maxn][maxn], lx[maxn], ly[maxn], fa[maxn];
bool S[maxn], T[maxn];

bool match(int i){
    S[i] = 1;
    for(int j = 1; j <= N; j++) if(lx[i] + ly[j] == w[i][j] && !T[j]){
        T[j] = 1;
        if(!fa[j] || match(fa[j])){
            fa[j] = i;
            return 1;
        }
    }
    return 0;
}

void update(){
    int a = INF;
    for(int i = 1; i <= N; i++) if(S[i])
        for(int j = 1; j <= N; j++) if(!T[j])
            a = min(a, lx[i] + ly[j] - w[i][j]);
    for(int i = 1; i <= N; i++){
        if(S[i]) lx[i] -= a;
        if(T[i]) ly[i] += a;
    }
}

void KM(){
    for(int i = 1; i <= N; i++){
        fa[i] = lx[i] = ly[i] = 0;
        for(int j = 1; j <= N; j++) lx[i] = max(lx[i], w[i][j]);
    }
    for(int i = 1; i <= N; i++)
        while(1){
            for(int j = 1; j <= N; j++) S[j] = T[j] = 0;
            if(match(i)) break;
            else update();
        }
}

void read(){
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++) scanf("%d", &w[i][j]);
}

void solve(){
    for(int i = 1; i < N; i++) printf("%d ", lx[i]); printf("%d\n", lx[N]);
    for(int i = 1; i < N; i++) printf("%d ", ly[i]); printf("%d\n", ly[N]);
    int sum = 0;
    for(int i = 1; i <= N; i++) sum += lx[i] + ly[i];
    printf("%d\n", sum);
}

int main()
{
    while(scanf("%d", &N) == 1){
        read();
        KM();
        solve();
    }
    return 0;
}

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101184.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pycharm编制索引_网页制作作品源代码

    pycharm编制索引_网页制作作品源代码tree/f/a>codeTree.txt

  • 【Java SE】————标识符及命名规则和关键字

    【Java SE】————标识符及命名规则和关键字Java标识符:             Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,其中,对于变量,常量,函数,语句块也有名字,我们统统称之为Java标识符.。       标识符是用来给类、对象、方法、变量、接口和自定义数据类型命名的。      Java标识符由数字,字母和下划线(_),美元符号($)组成。在Java中是区分大小写的,而且

  • 单片机的定时器_stm32的定时器有几个

    单片机的定时器_stm32的定时器有几个转载于:https://blog.csdn.net/tabactivity/article/details/99649928?depth_1-utm_source=distribute.pc_rele

  • C#操作XML的完整例子——XmlDocument篇「建议收藏」

    C#操作XML的完整例子——XmlDocument篇「建议收藏」这是一个用c#控制台程序下, 用XmlDocument进行XML操作的的例子,包含了查询、增加、修改、删除、保存的基本操作。较完整的描述了一个XML的整个操作流程。适合刚入门.netXML操作的朋友参考和学习。假设有XML文件:books.xmlxml version=”1.0″ encoding=”UTF-8″?>books> book>  name>哈里波特name>  pr

  • pandas apply() 函数用法

    pandas apply() 函数用法理解pandas的函数,要对函数式编程有一定的概念和理解。函数式编程,包括函数式编程思维,当然是一个很复杂的话题,但对今天介绍的apply()函数,只需要理解:函数作为一个对象,能作为参数传递给其它函数,并且能作为函数的返回值。函数作为对象能带来代码风格巨大的改变。举一个例子,有一个包含1到10的list,从其中找出能被3整除的数字。用传统的方法:defcan_divi…

  • Spring Security OAUTH2 获取用户信息

    Spring Security OAUTH2 获取用户信息1.user-info-uri与token-info-uri作用:二者皆是为了checktoken,并且顺带返回了用户信息。配置信息位置在资源服务器上。解释:下面代码列举的都是token-info-uri,user-info-uri不解释。user-info-uri原理是在授权服务器认证后将认证信息Principal通过形参绑定的方法通过URL的方式获取用户信息。当然它也有配套的Us…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号