hdu4888RedrawBeautifulDrawings

作者：npa3689305 | 来源：互联网 | 2023-12-12 11:54

本文介绍了一道网络流题目hdu4888RedrawBeautifulDrawings的解题思路。题目要求以行和列作为结点建图，并通过最大流算法判断是否有解以及是否唯一。文章详细介绍了建图和算法的过程，并强调在dfs过程中要进行回溯。

14多校第二题

网络流分别以行，列作为结点建图

i行表示的结点到j列表示的结点的流量便是(i, j)的值

跑遍最大流若满流了便是有解判断是否unique 就是在残余网络中dfs，走可以增加流量的边，找到环即不唯一

dfs的时候一定要回溯！！。。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;


//LOOP
#define FF(i, a, b) for(int i = (a); i <(b); ++i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i <(N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)


//OTHER
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define all(x) (x).begin(),(x).end()


//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define RS(s) scanf("%s", s)


//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(n) printf("%s\n", n)


//debug
//#define online_judge
#ifndef online_judge
#define dt(a)  <<(#a) <<"=" < VI;
const double eps = 1e-9;
const int MOD = 1000000007;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int maxn = 900;

bool use[maxn];
struct Edge{
    int from, to, cap, flow;
};
int MAX;

struct Dinic{
    int n, m ,s, t;
    vector edges;
    VI G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn]   ;

    void init(int nn)
    {
        this->n = nn;
        REP(i, n) G[i].clear();
        edges.clear();
    }

    void addEdge(int from, int to, int cap)
    {
        edges.PB((Edge){from, to, cap, 0});
        edges.PB((Edge){to, from, 0, 0});
        m = edges.size();
        G[from].PB(m - 2);
        G[to].PB(m - 1);
    }

    bool bfs()
    {
        CLR(vis, 0);
        queue Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty())
        {
            int x = Q.front();
            Q.pop();
            REP(i, G[x].size())
            {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int dfs(int x, int a)
    {
        if (x == t || a == 0)   return a;
        int flow = 0, f;
        for (int& i = cur[x]; i  0)
            {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int maxflow(int s, int t)
    {
        this-> s = s, this-> t = t;
        int flow = 0;
        while (bfs())
        {
            CLR(cur, 0);
            flow += dfs(s, INF);
        }
        return flow;
    }

    bool visit(int u, int fa)
    {
        if (u == 0 || u == MAX) return false;
        use[u] = 1;
        REP(i, G[u].size())
        {
            Edge& e = edges[G[u][i]];
//            debugII(e.to, use[e.to]);
            if (e.to != fa && e.cap > e.flow)
                if (use[e.to] || visit(e.to, u))
                    return true;
        }
        use[u] = 0;
        return false;
    }

}di;

int main()
{
    int n, m, k;
    while (~RIII(n, m, k))
    {
        int x, sum1 = 0, sum2 = 0;
        MAX = n + m + 1;
        di.init(n + m + 2);
        FE(i, 1, n)
        {
            RI(x);
            sum1 += x;
            di.addEdge(0, i, x);
        }
        FE(i, n + 1, n + m)
        {
            RI(x);
            sum2 += x;
            di.addEdge(i, n + m + 1, x);
        }
        FE(i, 1, n)
            FE(j, n + 1, n + m)
                di.addEdge(i, j, k);
        if (sum2 != sum1)
        {
            puts("Impossible");
            continue;
        }
        int ans = di.maxflow(0, n + m + 1);
        if (ans = di.edges.size())
                printf("\n");
            else
                printf(" ");
        }
        end:;
    }
    return 0;
}

hdu4888 Redraw Beautiful Drawings,,

hdu4888 Redraw Beautiful Drawings

推荐阅读

const
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
const
深入理解C++中的自定义String类实现

本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程，不仅能够检验开发者对C++基础知识的掌握程度，还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能，如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]

蜡笔小新 2024-11-22 19:21:22
const
HDU 6116 路径计数优化

本文探讨了使用普通生成函数和指数生成函数解决组合与排列问题的方法，特别是在处理特定路径计数问题时的应用。文章通过详细分析和代码实现，展示了如何高效地计算在给定条件下不相邻相同元素的排列数量。 ... [详细]

蜡笔小新 2024-11-22 13:11:20
bit
网络流24题——试题库问题

题目描述：假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]

蜡笔小新 2024-11-22 11:33:55
audio
深入解析Unity3D游戏开发中的音频播放技术

在游戏开发中，音频播放是提升玩家沉浸感的关键因素之一。本文将探讨如何在Unity3D中高效地管理和播放不同类型的游戏音频，包括背景音乐和效果音效，并介绍实现这些功能的具体步骤。 ... [详细]

蜡笔小新 2024-11-22 21:05:22
audio
CentOS 服务器自定义密码策略

随着Linux操作系统的广泛使用，确保用户账户及系统安全变得尤为重要。用户密码的复杂性直接关系到系统的整体安全性。本文将详细介绍如何在CentOS服务器上自定义密码规则，以增强系统的安全性。 ... [详细]

蜡笔小新 2024-11-22 19:15:42
audio
3DSMAX制作超现实的体育馆模型

这篇教程是向脚本之家的朋友介绍3DSMAX制作超现实的体育馆模型方法，教程制作出来的体育馆模型非常地不错，不过教程有点难度，需要有一定基础的朋友学习，推荐到脚本之家，喜欢的朋友可 ... [详细]

蜡笔小新 2024-11-22 16:07:10
function
AngularJS中ng-repeat元素的单选功能实现

本文介绍了如何在AngularJS应用中使用ng-repeat指令创建可单独点击选中的列表项，并详细描述了实现这一功能的具体步骤和代码示例。 ... [详细]

蜡笔小新 2024-11-22 15:56:12
function
冲刺最后一天的任务完成情况

在项目冲刺的最后一天，团队专注于软件用户界面的细节优化，包括调整控件布局和字体设置，以确保界面的简洁性和用户友好性。 ... [详细]

蜡笔小新 2024-11-22 14:51:19
function
JavaScript 页面卸载事件详解 (onunload)

当用户从页面离开时（如关闭页面或刷新页面），会触发 onunload 事件，此时可以执行预设的脚本。需要注意的是，不同的浏览器对 onunload 事件的支持程度可能有所不同。 ... [详细]

蜡笔小新 2024-11-22 14:17:44
config
如何将 Git 提交编辑器从 Nano 更改为 Vim

默认情况下，Git 使用 Nano 编辑器进行提交信息的编辑，但如果您更喜欢使用 Vim，可以通过简单的配置更改来实现这一变化。本文将指导您如何通过修改全局配置文件来设置 Vim 作为默认的 Git 提交编辑器。 ... [详细]

蜡笔小新 2024-11-22 14:08:35
config
探索Java 11中的ZGC垃圾收集器

Java 11引入了一种新的垃圾收集器——ZGC，由Oracle公司研发，旨在支持TB级别的内存容量，并保证极低的暂停时间。本文将探讨ZGC的开发背景、技术特点及其潜在的应用前景。 ... [详细]

蜡笔小新 2024-11-22 13:36:53
spring
我的读书清单（持续更新）

我的读书清单（持续更新）201705311.《一千零一夜》2006（四五年级）2.《中华上下五千年》2008（初一）3.《鲁滨孙漂流记》2008（初二）4.《钢铁是怎样炼成的》20 ... [详细]

蜡笔小新 2024-11-21 13:01:23
select
IC卡操作功能实现

本文介绍了如何通过C#语言调用动态链接库（DLL）中的函数来实现IC卡的基本操作，包括初始化设备、设置密码模式、获取设备状态等，并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]

蜡笔小新 2024-11-21 11:02:19
const
深入理解C++构造函数

本文详细介绍了C++中的构造函数，包括其定义、特点以及如何通过构造函数进行对象的初始化。此外，还探讨了转换构造函数的概念及其在不同情境下的应用，以及如何避免不必要的隐式类型转换。 ... [详细]

蜡笔小新 2024-11-21 10:41:14

npa3689305

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章