最小割

HDU 6126 Give out candies

Posted on

Table of contents

例行废话

哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼……

我学了这么久的图论究竟是为了什么呢……
老实说我有一种不详的预感

现在想想的确是这样的,自己努力钻研的高级算法,又有多少会在比赛中用到呢……

回归正题

这是一道最小割+差分约束的题目,还是第一次遇到这两个结合起来。不过其实也只是分开来的问题,用差分约束判断可行性,再用最小割求解。

题意:
你要给\( n\) 个小朋友糖果,最少\( 1\)个,最多\( m \)个,并且你手上有无穷多的糖。并不是说给一个小朋友的糖果越多越好,给每一个小朋友不同糖果数量对应的愉悦值不同。我们自然希望小朋友的愉悦值最大化。
但这些小朋友也提出了一些要求,对于每一个要求\( ( x , y , z ) \),你给 \( x\) 的糖果数量 \( ax \) 与给\( y\) 的糖果数量\( ay\) 满足如下不等式 \( ax - ay \leq z \)。
问满足所有要求的最大愉悦值。
若无法满足,输出-1。

思路:

关于满足小朋友们的要求
这是整个问题的一个子问题,每个要求都是一个不等式,我们很自然地能够想到用差分约束去判断可行性。这个子问题是个差分约束的裸问题,这里不再赘述。

关于最小割建图
先直接上建图方式,下面有解释。
设源点\( S \) ,汇点\( T\) ,\( ( a , b ) \)表示给小朋友\( a\) 糖果 \( b \) 颗。
\( a \rightarrow b == c \) 表示 \( a\) 与 \( b\) 建边,容量为 \( c \)。

  • 对于每一个小朋友 \( p\) \( S \rightarrow ( p, 1 ) == inf , ( p , m ) \rightarrow T ==inf \)
  • 对于每一个小朋友 \( p\) 的每一个给定糖果数量 \( k\) 所得的愉悦值 \( w\) ,\( ( p, k ) \rightarrow ( p , k+1 ) \),注意后面不能越界。
  • 对于每一个限制要求 \( ax - ay \leq z \),再对于范围内的糖果数量 \( i\) ,建边\( ( x , i + z ) \rightarrow ( y , i ) == inf \)

因为给每个小朋友的糖果数量 \( w \leq 1000 \) 。( 题面上并没有说明,但是题解上说了…… )
那么我们可以这么想,我先给每个小朋友 1000 个糖果,然后再从小朋友中拿回一些糖果,我们要求最大值,自然是使得拿回的糖果造成的愉悦值减少最小,对于一个小朋友来说这就是一条割边。因为每个小朋友都要拿回糖果,所以对于整张图来说就是最小割了。

再是对每一个限制要求:写个题解好累,能自己理解去么……
对于\( (x , i + z ) \rightarrow ( y , i ) \) 可以这样想,如果我割掉了 \( ( x, i + z - 1 ) \rightarrow ( x , i + z ) \) ,那么如果你在 \( y\)不选择\( ( y, i ) \) 之后的边,那么上面那个割边就变的没有意义,从而你必须去割掉一条 \( inf\) 的边。
哎呀,自己在纸上画画就很清楚了……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef pair<int, int> pii;
const int maxv = 55;
const int maxn = maxv * maxv;
const int maxm = maxn * maxn;
const int inf = 0x3f3f3f3f;

int n, m, k, st, en, idx;
int cur[maxn], level[maxn], head[maxn];
int kvis[maxv];

int mat[maxv][maxv];
int ku[155], kv[155], kw[155];

vector<pii> G[55];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;
stack<int> stk;

inline int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void Ginit()
{
    memset(kvis, false, sizeof kvis);
    for (int i = 0; i < n; i++)
        G[i].clear();
}

void init(int s, int e)
{
    st = s, en = e;
    memset(head, -1, sizeof head);
    idx = 0;
}

bool spfa(int st)
{
    bool vis[maxv];
    int dis[maxv], cnt[maxv];
    for (int i = 0; i <= n; i++) {
        cnt[i] = vis[i] = false;
        dis[i] = inf;
    }
    while (!stk.empty())
        stk.pop();
    dis[st] = 0, kvis[st] = vis[st] = true, cnt[st] = 1;
    stk.push(st);
    while (!stk.empty()) {
        int u = stk.top(), sz = G[u].size();
        stk.pop();
        vis[u] = false;
        for (int i = 0; i < sz; i++) {
            int v = G[u][i].first;
            if (dis[v] > dis[u] + G[u][i].second) {
                dis[v] = dis[u] + G[u][i].second;
                if (!vis[v]) {
                    kvis[v] = vis[v] = true;
                    stk.push(v);
                    if (++cnt[v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

void CreateGragh()
{
    m++;
    init(n * m, n * m + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++)
            addEdge(getNode(i, j), getNode(i, j + 1), 1000 - mat[i][j]);
        addEdge(st, getNode(i, 0), inf);
        addEdge(getNode(i, m - 1), en, inf);
    }
    for (int p = 0; p < k; p++) {
        for (int i = 0; i + kw[p] < m; i++)
            addEdge(getNode(ku[p], i + kw[p]), getNode(kv[p], i), inf);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &mat[i][j]);
        Ginit();
        for (int i = 0; i < k; i++) {
            scanf("%d %d %d", ku + i, kv + i, kw + i);
            ku[i]--, kv[i]--;
            G[ku[i]].push_back(make_pair(kv[i], kw[i]));
        }
        bool flag = false;
        for (int i = 0; i < n && !flag; i++)
            if (!kvis[i])
                if (!spfa(i)) {
                    flag = true;
                    break;
                }
        if (flag) {
            puts("-1");
            continue;
        }
        CreateGragh();
        int key = dinic();
        printf("%d\n", 1000 * n - key);
    }
    return 0;
}
差分约束

HDU 1534 Schedule Problem

Posted on

应该是很明显的差分约束的题目了 只要想清楚 节点的含义 路径的含义 建好模 就好说
这里我直接设 d[I] 表示 第i个事件的开始时间
根据题意 可得

FAS:d[u]+val[u]>=d[v]
FAF:d[u]+val[u]>=d[v]+val[v]
SAF:d[u]>=d[v]+val[v]
SAS:d[u]>=d[v]

题目要求最小值,需要转化为:

d[u]--d[v]>=-val[u]
d[u]-d[v]>=val[v]-val[u]
d[u]-d[v]>=val[v]
d[u]-d[v]>=0

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int n,idx;
int d[maxn],val[maxn],head[maxn],cnt[maxn];
bool vis[maxn];

struct node
{
    int v,w;
    int nxt;
}edge[maxn];

void init()
{
    for(int i=0;i<=n;i++)
    {
        head[i]=-1;
        d[i]=-inf;
        vis[i]=false;
        cnt[i]=0;
    }
    idx=0;
}

void add(int u,int v,int w)
{
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}

bool spfa()
{
    vis[0]=true;
    d[0]=0;
    queue<int> que;
    que.push(0);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int id=head[u];id!=-1;id=edge[id].nxt)
        {
            int v=edge[id].v;
            if(d[u]+edge[id].w>d[v])
            {
                d[v]=d[u]+edge[id].w;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    char ch[5];
    int u,v,cas=0;
    while(scanf("%d",&n),n)
    {
        init();
        for(int i=1;i<=n;i++) scanf("%d",val+i);
        scanf("%s",ch);
        while(ch[0]!='#')
        {
            scanf("%d %d",&u,&v);
            if(ch[0]=='S')
            {
                if(ch[2]=='S') add(v,u,0);
                else add(v,u,val[v]);
            }
            else
            {
                if(ch[2]=='S')
                    add(v,u,-val[u]);
                else add(v,u,val[v]-val[u]);
            }
            scanf("%s",ch);
        }
        printf("Case %d:\n",++cas);
        for(int i=1;i<=n;i++) add(0,i,0);
        if(spfa()) for(int i=1;i<=n;i++) printf("%d %d\n",i,d[i]);
        else puts("impossible");
        puts("");
    }
    return 0;
}