HDU 4975 最大流+判断环_最大流问题有环-程序员宅基地

技术标签: 线段树  图论  最大流  HDU  网络流  ACM  

点击打开链接

题意:给定的分别是每行值的和,每列值的和,每个元素的值在0~9之间,问有多少种情况符合条件,多种,一种和不可能分别输出三种情况

思路:刚读完题根本没有思路,看了网上的才知道用网络流,那样的话就好办了,建个源点,与每行建一条流量为行和的边,每一列与汇点建一条流量为列和的边,每行与每列建一条流量为9的边,跑最大流后判断是否满流就行了,但是要怎么判断有没有多组解呢,当残余网络中有环时,我们可以调整这个环来符合条件,将一条边加1,则另一条边可以减去1,所以判断残余网络中有没有大于2的环,并不会......,看大多数题解都是dfs回溯时删边或者删点,并不会,然后我的做法是将可行的边先预处理出来,然后非常暴力的dfs,一不小心400ms过了.......

#include <queue>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1010;
struct edge{
    int to,cap,rev;
    edge(int a,int b,int c){to=a;cap=b;rev=c;}
};
vector<edge>G[maxn];
vector<int>G1[maxn];
int level[maxn],iter[maxn],vis[maxn],n,m;
void addedge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
}
void add_edge(int from,int to){
    G1[from].push_back(to);
}
void bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int>que;level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        for(unsigned int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t){
    int flow=0;
    while(1){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,inf))>0) flow+=f;
    }
}
bool Judge_dfs(int x,int val){
    vis[x]=1;
    for(unsigned int i=0;i<G1[x].size();i++){
        int t=G1[x][i];
        if(t==val) continue;
        if(vis[t]) return 1;
        if(Judge_dfs(t,x)) return 1;
    }
    vis[x]=0;
    return 0;
}
bool judge(){
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n+m+1;i++){
        for(unsigned int j=0;j<G[i].size();j++){
            edge &e=G[i][j];
            if(e.cap>0) add_edge(i,e.to);
        }
    }
    for(int i=0;i<=n;i++){
        if(Judge_dfs(i,-1)) return 1;
    }
    return 0;
}
int main(){
    int T,a,b,t=1;
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<maxn;i++){
            G[i].clear();
            G1[i].clear();
        }
        scanf("%d%d",&n,&m);
        int sum=0,sum1=0,sum2=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a);sum+=a;sum1+=a;
            addedge(0,i,a);
        }
        for(int j=1;j<=m;j++){
            scanf("%d",&b);sum2+=b;
            addedge(j+n,n+m+1,b);
        }
        if(sum1!=sum2){
            printf("Case #%d: So naive!\n",t++);
            continue;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                addedge(i,j+n,9);
        }
        int ans=max_flow(0,n+m+1);
        if(ans!=sum) printf("Case #%d: So naive!\n",t++);
        else{
            if(judge()) printf("Case #%d: So young!\n",t++);
            else printf("Case #%d: So simple!\n",t++);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Dan__ge/article/details/51095450

智能推荐

IOS学习—强引用(__strong)和 弱引用(__weak)_ios __strong-程序员宅基地

文章浏览阅读2.6k次。转载于开源中国在Objective-C的ARC模式中,id obj1 = [[NSObject alloc] init]; 这里虽然没有显示的声明为__strong,但是Objective-C默认声明的一个对象就为__strong,即: id obj1 = [[NSObject alloc] init]; 和 id __strong obj1 = [[NSObject alloc] init_ios __strong

ubuntu18.04下qt5.9编译错误: -1: error: cannot find -lGL_:-1: error: /usr/local/qt-5.9/lib/libqt5core.so: u-程序员宅基地

文章浏览阅读2.1k次。只要安装libGL即可:sudo apt-get install libqt4-devsudo apt update再重新编译就ok啦 _:-1: error: /usr/local/qt-5.9/lib/libqt5core.so: undefined reference to `uca

如何绘制深度神经网络图_深度学习神经网络图怎么画-程序员宅基地

文章浏览阅读2.7k次,点赞4次,收藏22次。1.在线版本的NN-SVG_深度学习神经网络图怎么画

菜鸟学习Android笔记-20140311_textview3:[i18n] hardcoded string-程序员宅基地

文章浏览阅读771次。1、编写布局文件时,遇到这样的警告,“[I18N] Hardcoded string "昵称:", should use @string resource” 原来的代码:

不同参数统计运行时间 large_integer c语言,使用LARGE_INTEGER查看系统运行时间-程序员宅基地

文章浏览阅读252次。众所周知,windows ce是一个实时操作,因此提供了不少的优先级给用户.优先级最高为0级,也就是说使用0优先级的程序, 可以挂起整个系统, 来运行你的程序对于实时性比较的领域, 我们作为程序员的 应该清楚的知道你的程序模块运行的时间 是非常必要的. 当然这个模块运行的时间也不是完全的稳定的, 几次运行的时间相差几十毫秒是很正常的. 因此我们只要知道大概的时间就可以了.当然, 大家..._large_integer计算时间

ssh登陆服务器locale告警(-bash: warning: setlocale:)的处理方法-程序员宅基地

文章浏览阅读1.9k次。 使用ssh远程登陆 IDC机房服务器,发现老是出现如下告警信息:-bash: warning: setlocale: LC_CTYPE: cannot change locale (en_US.UTF-8): No such file or directory-bash: warning: setlocale: LC_COLLATE: cannot change locale (en_U..._bash: warning: setlocale: lc_ctype: cannot change locale (en_us.utf-8): no s

随便推点

SQL中IF ELSE及MySQL伪列rownum的使用_mysql 如何使用if else 生成伪列-程序员宅基地

文章浏览阅读290次。编写SQL语句时难免会遇到各种条件判断,例如统计:count(case when then end)今天,我们要说的是if判断,eg:SELECT IF(c19='1','已评价','未评价')c19 FROM A05;关于伪列,广为人知的是oracle有伪列rownum,因为一些需求需要用mysql实现类似Oracle的伪列,方法方式如下:SELECT rowid, i01..._mysql 如何使用if else 生成伪列

【C++】虚函数及其内存布局_c++虚函数内存分布-程序员宅基地

文章浏览阅读1.7k次,点赞5次,收藏20次。一、函数调用捆绑把函数体与函数调用相联系称为捆绑。当捆绑在程序运行之前(由编译器和连接器)完成时,称为早捆绑。C编译只有一种函数调用方式,就是早捆绑。早捆绑引起的问题:因为编译器在只有对象的地址时它并不知道要调用的正确函数。根据对象的类型,捆绑发生在运行时,这种捆绑方式称为晚捆绑,又称动态捆绑。二、虚函数对于特定的函数,为了引起晚捆绑,C++要求在基类中声明这个函数时使用virtual关键字,这样的函数称为虚函数。晚捆绑只对virtual函数起作用,而且只在使用含有virtual函._c++虚函数内存分布

matlab 相位校正,科学网—全相位比值校正法 - 王兆华的博文-程序员宅基地

文章浏览阅读709次。加hann窗全相位比值校正法和加hann窗fft比值校正法校正方法类同,只须将二个振幅比改为振幅开方比即可。这里加hann窗是关键,过去测试时,直接调用Matlab中的hann(N)窗,频率和振幅校正效果差,见表5加hann窗全相位比值校正法测试结果。表4为加n-hann窗全相位比值校正法,其频率校正精度,相位校正精度和振幅校正精度都很高,甚至可以和表1加n-hann卷积窗apfft/apfft校..._比值校正法频谱校正matlab

创建登录界面_建网站登录页面-程序员宅基地

文章浏览阅读334次。package zhoushi;import javax.swing.*;//调用库import java.awt.*;import java.awt.event.*;public class jh extends JFrame implements ActionListener{//创建类jh继承JFrame,实现接口ActionListener JPanel log;//定义变量_建网站登录页面

win10安装linux虚拟机并配置shell工具连接_shell确认虚拟机光盘连接-程序员宅基地

文章浏览阅读1k次。1:虚拟机安装先看怎么用VMware安装一个虚拟机,全部放图,一步步来。主要还是以防以后我自己忘记怎么搞了,老了,记性不好了。VMware就在网上随便下载一个了,镜像我会在下面放上我的或者大家也可以自己去网上下一个。第一步:新建虚拟机第二步:选择类型第三步:选择映像文件,一般都会检测到,检测不到就只能自己打开浏览去找吧!第四步:给虚拟机命名,可以更改虚拟机安装位置。反正我是不会装在系统盘的,这辈子都不会的o(´^`)o第五步:默认选择是虚拟磁盘拆分成多个文件,但._shell确认虚拟机光盘连接

计算机视觉模型常用评价指标_平均交并比-程序员宅基地

文章浏览阅读3.6k次,点赞9次,收藏36次。分类任务常用准确率、精确率、召回率、F1_scores、ROC曲线等指标来评价模型的优劣,当然这些基础指标也可以用来评价分割模型或检测模型,它们基本上是可以通用的。混淆矩阵是对分类问题预测结果的总结,也是衡量分类型模型准确度中最基本,最直观,计算最简单的方法。混淆矩阵中含有4个分类问题的基础指标,如下表所示。........._平均交并比