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

推荐阅读

include
[c++基础]STL

cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]

蜡笔小新 2024-11-13 13:22:43
merge
ASP.NET 中操作 Excel 的常见方法和属性

本文介绍了如何在 ASP.NET 中设置 Excel 单元格格式为文本，获取多个单元格区域并作为表头，以及进行单元格合并、赋值、格式设置等操作。 ... [详细]

蜡笔小新 2024-11-13 19:46:18
io
SoundPool

如果应用程序经常播放密集、急促而又短暂的音效（如游戏音效）那么使用MediaPlayer显得有些不太适合了。因为MediaPlayer存在如下缺点：1)延时时间较长，且资源占用率高 ... [详细]

蜡笔小新 2024-11-13 16:47:19
js
Pythonmysql数据库

importpymysql#一、直接连接mysql数据库'''coonpymysql.connect(host'192.168.*.*',u ... [详细]

蜡笔小新 2024-11-12 16:51:59
io
解决Bootstrap DataTable Ajax请求重复问题

在最近的一个项目中，我们使用了JQuery DataTable进行数据展示，虽然使用起来非常方便，但在测试过程中发现了一个问题：当查询条件改变时，有时查询结果的数据不正确。通过FireBug调试发现，点击搜索按钮时，会发送两次Ajax请求，一次是原条件的请求，一次是新条件的请求。 ... [详细]

蜡笔小新 2024-11-12 13:59:27
io
第二十五天接口、多态

1.java是面向对象的语言。设计模式：接口接口类是从java里衍生出来的，不是python原生支持的主要用于继承里多继承抽象类是python原生支持的主要用于继承里的单继承但是接 ... [详细]

蜡笔小新 2024-11-12 06:43:20
uri
解决Parallels Desktop错误15265的方法

本文详细介绍了在使用Parallels Desktop时遇到错误15265的多种解决方案，包括检查网络连接、关闭代理服务器和修改主机文件等步骤。 ... [详细]

蜡笔小新 2024-11-12 05:14:12
io
解决 Windows Server 2016 网络连接问题

本文详细介绍了如何解决 Windows Server 2016 在使用无线网络 (WLAN) 和有线网络 (以太网) 时遇到的连接问题。包括添加必要的功能和安装正确的驱动程序。 ... [详细]

蜡笔小新 2024-11-12 00:01:44
js
使用Jsoup解析并遍历HTML文档结构

使用Jsoup解析并遍历HTML文档时，该库能够高效地生成一个清晰、规范的解析树，即使源HTML文档存在格式问题。Jsoup具备强大的容错能力，能够处理多种异常情况，如未闭合的标签等，确保解析结果的准确性和完整性。 ... [详细]

蜡笔小新 2024-11-11 21:30:03
io
LDAP服务器配置与管理

本文介绍如何通过安装和配置SSSD服务来统一管理用户账户信息，并实现其他系统的登录调用。通过图形化交互界面配置LDAP服务器，确保用户账户信息的集中管理和安全访问。 ... [详细]

蜡笔小新 2024-11-13 18:19:52
io
网络爬虫的规范与限制

本文探讨了网络爬虫引发的问题及其解决方案，重点介绍了Robots协议的作用和使用方法，旨在为网络爬虫的合理使用提供指导。 ... [详细]

蜡笔小新 2024-11-13 15:45:41
js
AngularJS $compile 详解

本文介绍了 AngularJS 中的 $compile 服务及其用法，通过示例代码展示了如何使用 $compile 动态编译和链接 HTML 元素。 ... [详细]

蜡笔小新 2024-11-13 15:34:47
js
自动验证时页面显示问题的解决方法

在使用自动验证功能时，页面未能正确显示错误信息。通过使用 `dump($info->getError())` 可以帮助诊断和解决问题。 ... [详细]

蜡笔小新 2024-11-13 12:30:21
include
解决DNS服务器配置转发无法解析的问题

本文详细介绍了如何解决DNS服务器配置转发无法解析的问题，包括编辑主配置文件和重启域名服务的具体步骤。 ... [详细]

蜡笔小新 2024-11-13 02:41:19
js
DMA控制器与外设请求映射表详解

本文详细介绍了DMA控制器如何通过映射表处理来自外设的请求，包括映射表的设计和实现方法。 ... [详细]

蜡笔小新 2024-11-12 13:51:55

npa3689305

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

Tags | 热门标签

RankList | 热门文章