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

推荐阅读

java
病毒特征检测 - AC自动机应用

题目描述了一个病毒检测问题，要求使用AC自动机算法统计目标文本中多个模式串的出现次数。 ... [详细]

蜡笔小新 2024-12-14 17:53:50
io
C语言编程课程第十二课

本课程将深入探讨C语言中的数组操作与基本算法实现，包括最大最小值交换、数组旋转以及约瑟夫环问题等经典案例分析。 ... [详细]

蜡笔小新 2024-12-13 19:45:46
java
JS的类型和值

1.类型ECMAScript语言中所有的值都有一个对应的语言类型。ECMAScript语言类型包括Undefined、Null、Boolean、String、Number和Obje ... [详细]

蜡笔小新 2024-12-12 22:45:35
default
Arcgis for Js实现graphiclayer的空间查询（续）

详细的介绍针对graphiclayer的空间查询。首先，空间查询的方式：提供多种类型的空间查询，包括点周边、线周边、面内等多种方式；其次，图形绘制完成后状态的展示；再次 ... [详细]

蜡笔小新 2024-12-14 21:28:17
bit
iftop：网络流量实时监控工具

本文介绍了iftop的下载地址、基本参数配置方法及其在不同Linux发行版中的安装问题解决方案。iftop是一款强大的实时网络流量监控工具，适用于需要精确监控网络带宽使用情况的场景。 ... [详细]

蜡笔小新 2024-12-14 19:18:23
bit
解决Firefox中HTML5 Canvas drawImage NS_ERROR_NOT_AVAILABLE错误

在使用Firefox浏览器打开本地HTML文件时，尝试调用Canvas的drawImage方法可能会遇到NS_ERROR_NOT_AVAILABLE错误。本文探讨了这一问题的原因及解决方案。 ... [详细]

蜡笔小新 2024-12-13 22:02:02
io
Python库在GIS与三维可视化中的应用

Python库极大地扩展了GIS的能力，使其能够执行复杂的数据科学任务。本文探讨了几个关键的Python库，这些库不仅增强了GIS的核心功能，还推动了地理信息系统向更高层次的应用发展。 ... [详细]

蜡笔小新 2024-12-13 17:24:24
io
探索邵杨的代码库

2014年4月17日，深入研究了邵杨的代码库，发现代码中的注释较为稀少，影响了理解的效率。同时，学习了一些Eclipse的高效操作技巧。 ... [详细]

蜡笔小新 2024-12-13 16:28:47
bit
Linux 文件系统中的特殊权限详解：SUID、SGID 和 Sticky Bit

在 Linux 系统中，除了基本的读取、写入和执行权限外，还存在三种特殊权限：Set User ID (SUID)、Set Group ID (SGID) 和 Sticky Bit。这些特殊权限用于增强系统的安全性和功能性。 ... [详细]

蜡笔小新 2024-12-13 14:55:42
bit
第四天冲刺：记账本与蓝牙聊天功能进展

在今天的开发过程中，团队对记账本应用的用户界面进行了初步设计，并讨论了加入自动累计功能的可能性。此外，蓝牙聊天功能已基本实现，但界面设计仍需改进。 ... [详细]

蜡笔小新 2024-12-13 14:46:59
default
Java Swing界面编程(31)菜单栏：JMenu

如何打造属于自己程序的菜单栏，以上代码清晰的展示了swing是如何创建菜单栏的。只要理清楚javaswing的容器和面板的逻辑顺序就能掌握swing ... [详细]

蜡笔小新 2024-12-13 11:19:09
default
深入理解Android NinePatch图片在聊天界面的应用

本文探讨了在开发Android应用，特别是聊天界面时，如何有效利用NinePatch图片解决图片拉伸问题。文章通过实例展示了不使用与使用NinePatch图片的区别，并详细介绍了如何创建和使用NinePatch图片。 ... [详细]

蜡笔小新 2024-12-13 10:41:40
default
[世预赛] 中国vs关岛，关岛实力有限国足或许可以赢其10个球，比分预测 10:0，8:0，13:0

[世预赛] 中国vs关岛开赛时间：2019-10-1020:00继5比0大胜马尔代夫之后，国足迎来世预赛40强赛的第二场比赛，再次向世界杯发起冲击。10月10日，国足在广州迎战神秘 ... [详细]

蜡笔小新 2024-12-13 10:08:05
default
SQL入门：深入理解DELETE与UPDATE操作

本文详细介绍了SQL中的DELETE和UPDATE命令，包括它们的基本语法、应用场景以及如何通过这些命令高效地管理数据库中的数据。重点解释了DELETE用于删除数据行，而UPDATE则用于更新数据行中的特定字段值。 ... [详细]

蜡笔小新 2024-12-13 08:07:14
go
深入理解MooseFS副本管理和回收机制

本文详细介绍了MooseFS中的副本管理（Goal）以及文件回收机制。副本管理允许用户设定文件的复制份数，确保数据的安全性和可用性；而文件回收机制则提供了在误删除文件后的恢复途径，通过设置合理的隔离时间，保护重要数据。 ... [详细]

蜡笔小新 2024-12-12 21:23:50

npa3689305

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

Tags | 热门标签

RankList | 热门文章