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

推荐阅读

buffer
Python学习笔记：使用pydoc工具查询文档

本文介绍了在Windows环境下使用pydoc工具的方法，并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外，还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]

蜡笔小新 2024-12-26 17:05:56
js
QUIC协议：快速UDP互联网连接

QUIC（Quick UDP Internet Connections）是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP，并结合了TLS级别的安全性，提供了更高效、更可靠的互联网通信方式。 ... [详细]

蜡笔小新 2024-12-28 12:33:18
js
深入理解 Oracle 存储函数：计算员工年收入

本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]

蜡笔小新 2024-12-28 09:49:42
js
深入理解Cookie与Session会话管理

本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]

蜡笔小新 2024-12-27 18:20:43
copy
Linux 自动化安装脚本详解

本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建，还处理了系统服务的配置和启动，确保在多种 Linux 发行版上都能顺利运行。 ... [详细]

蜡笔小新 2024-12-27 16:33:32
js
使用Windows批处理脚本监控并重启Java应用程序

本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序，确保其持续稳定运行。脚本每30分钟检查一次，并在需要时重启Java程序。同时，它会将任务结果发送到Redis。 ... [详细]

蜡笔小新 2024-12-27 10:44:39
js
使用 NSTimer 实现倒计时功能

本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

蜡笔小新 2024-12-26 19:08:19
js
深入理解OAuth认证机制

本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准，旨在为第三方应用提供安全的用户资源访问授权，同时确保用户的账户信息（如用户名和密码）不会暴露给第三方。 ... [详细]

蜡笔小新 2024-12-28 12:07:46
js
如何在WPS Office for Mac中调整Word文档的文字排列方向

本文将详细介绍如何使用最新版WPS Office for Mac调整Word文档中的文字排列方向。通过这些步骤，用户可以轻松更改文本的水平或垂直排列方式，以满足不同的排版需求。 ... [详细]

蜡笔小新 2024-12-27 12:34:14
js
存储器层次结构、随机访问存储器与数据存取机制

理解存储器的层次结构有助于程序员优化程序性能，通过合理安排数据在不同层级的存储位置，提升CPU的数据访问速度。本文详细探讨了静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）的工作原理及其应用场景，并介绍了存储器模块中的数据存取过程及局部性原理。 ... [详细]

蜡笔小新 2024-12-27 12:06:47
js
几何画板展示电场线与等势面的交互关系

几何画板是一款功能强大的物理教学软件，具备丰富的绘图和度量工具。它不仅能够模拟物理实验过程，还能通过定量分析揭示物理现象背后的规律，尤其适用于难以在实际实验中展示的内容。本文将介绍如何使用几何画板演示电场线与等势面之间的关系。 ... [详细]

蜡笔小新 2024-12-27 10:46:07
js
MySQL中枚举类型的所有可能值获取方法

本文介绍了一种在MySQL数据库中查询枚举（ENUM）类型字段所有可能取值的方法，帮助开发者更好地理解和利用这一数据类型。 ... [详细]

蜡笔小新 2024-12-27 10:36:44
char
实现密码输入框的掩码设置

本文介绍如何在应用程序中使用文本输入框创建密码输入框，并通过设置掩码来隐藏用户输入的内容。我们将详细解释代码实现，并提供专业的补充说明。 ... [详细]

蜡笔小新 2024-12-27 02:22:09
js
从JDE系统中提取完整字典数据

本文介绍如何通过SQL查询从JDE（JD Edwards）系统中提取所有字典数据，涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]

蜡笔小新 2024-12-26 21:04:46
js
启动MySQL服务的命令行步骤

本文详细介绍了如何通过命令行启动MySQL服务，包括打开命令提示符窗口、进入MySQL的bin目录、输入正确的连接命令以及注意事项。文中还提供了更多相关命令的资源链接。 ... [详细]

蜡笔小新 2024-12-26 20:16:36

npa3689305

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

Tags | 热门标签

RankList | 热门文章