DQS DQS

HIT Summer Training Day13 最大流|费用流

in 算法,网络流,图论,模拟赛read (191) 文章转载请注明来源!

网络流忘干净了!!

zkw费用流大法吼!!(虽然不会

还有这场大部分题我好像都做过……


A : hoj - 1646

给一个无向图,问最少删多少个点使其不连通。

无向图点连通度,可以把每个点拆点,连边容量为1。原图中的边设为INF防割。

可以固定源点枚举汇点,跑最小割然后取min就行了。

代码我写的枚举源汇点,其实源点不需要枚举……

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 100010;
const int INF = 1000000010;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;

bool isin(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

struct edge{
    int t,d;
}l[1000010];

void build(int f,int t,int d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,int d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

int dfs(int u,int flow)
{
    if(u == e || flow == 0) return flow;
    int rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            int f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        int tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}
int ff[SZ],tt[SZ];

void build_graph()
{
    memset(head,0,sizeof(head)); tot = 1;
    for(int i = 1;i <= m;i ++)
        insert(ff[i] + n,tt[i],INF),insert(tt[i] + n,ff[i],INF);
    insert(s,s + n,INF),insert(s + n,s,INF);
    insert(e,e + n,INF),insert(e + n,e,INF);
    for(int i = 1;i <= n;i ++)
    {
        if(i == s || i == e) continue;
        insert(i,i + n,1),insert(i + n,i,1);
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= m;i ++)
            scanf(" (%d,%d)",&ff[i],&tt[i]),ff[i] ++,tt[i] ++;
        int ans = INF;
        for(int i = 1;i <= n;i ++)
        {
            for(int j = i + 1;j <= n;j ++)
            {
                s = i,e = j;
                build_graph();
                int tmp = dinic();
                ans = min(ans,tmp);
            }
        }
        if(ans == INF || n == 1) printf("%d\n",n);
        else printf("%d\n",ans);
    }
    return 0;
}


B : hdu - 1569

最大点权独立集。经典最小割模型。

具体做法是:最大点权独立集=总点权-最小点权覆盖集

对于两个相邻格子,连边表示他们两个相邻,连边为INF防割。

将图黑白染色,这样变成了二分图。源点向白点连边,容量为这个点的权值。汇点向黑点连边,容量为权值。

原问题为:对于中间的INF边,左右两点至少选一个(因为点权必定为正)

如果跑网络流,那么割边一定是左右两点连向源/汇点之一,表示选中它。

这样就得到了最小点权覆盖集,减去即为最大点权独立集。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 10010;
const int INF = 1000000010;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;

bool isin(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

struct edge{
    int t,d;
}l[1000010];

void build(int f,int t,int d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,int d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

int dfs(int u,int flow)
{
    if(u == e || flow == 0) return flow;
    int rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            int f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        int tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}

int get_id(int x,int y,int t)
{
    return (x - 1) * m + y + t * n * m;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,0,sizeof(head)); tot = 1;
        int sum = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                int x = read();
                insert(get_id(i,j,0),get_id(i,j,1),x);
                sum += x;
                if(!((i + j) & 1))
                    for(int k = 0;k < 4;k ++)
                    {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if(isin(x,y))
                            insert(get_id(i,j,1),get_id(x,y,0),INF);
                    }
            }
        s = n * m * 2 + 1,e = s + 1;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(!((i + j) & 1))
                    insert(s,get_id(i,j,0),INF);
                else
                    insert(get_id(i,j,1),e,INF);
        printf("%d\n",sum - dinic());
    }
    return 0;
}


C : hdu - 5855

对于一些商店,建成后有一个一次性收益$pro_i$,建成某个商店必须先建成一些工厂,他们有一个建成时间$t_i$和花费$pay_i$。工厂可以一起同时建造。问总利润达到L最少需要多少天,和在这个天数中能得到的最大收益。

可以发现不看时间就是经典的最大权闭合子图问题……这个问题就是G,放后面说。

所以可以二分时间T,然后就完了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1010;
const LL INF = 100000000000000010ll;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;


struct edge{
    int t;
    LL d;
}l[1000010];

void build(int f,int t,LL d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,LL d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

LL dfs(int u,LL flow)
{
    if(u == e || flow == 0) return flow;
    LL rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            LL f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

LL dinic()
{
    LL ans = 0;
    while(bfs())
    {
        LL tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}

LL pay[SZ],pro[SZ],tim[SZ];
LL sum = 0;
vector<int> g[SZ];

void build_graph(int mid)
{
    memset(head,0,sizeof(head)); tot = 1;
    for(int i = 1;i <= m;i ++)
        insert(s,i,pro[i]);
    for(int i = m + 1;i <= m + n;i ++)
        if(tim[i] <= mid)
            insert(i,e,pay[i]);
        else
            insert(i,e,INF);
    for(int i = 1;i <= m;i ++)
    {
        for(int j = 0;j < g[i].size();j ++)
            insert(i,g[i][j],INF);
    }
}

int L;

int Div()
{
    int l = 0,r = 1000000001;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        build_graph(mid); LL ans = dinic();
//        cout << mid << " " << ans << endl;
        if(sum - ans < L) l = mid;
        else r = mid;
    }
    return r;
}


int main()
{
    int cc = 0;
    int T = read();
    while(T --)
    {
        scanf("%d%d%d",&n,&m,&L);
        sum = 0;

        s = n + m + 1,e = n + m + 2;
        for(int i = m + 1;i <= m + n;i ++)
            pay[i] = read(),tim[i] = read();
        for(int i = 1;i <= m;i ++)
        {
            pro[i] = read(); g[i].clear();
            sum += pro[i];
            int k = read();
            while(k --)
                g[i].push_back(read() + m);
        }
        printf("Case #%d: ",++ cc);
        int ans = Div();
        if(ans == 1000000001) puts("impossible");
        else
        {
            build_graph(ans);
            printf("%d %lld\n",ans,sum - dinic());
        }
    }
    return 0;
}


D : poj - 3680

给n个开区间(包括非整数),区间覆盖的点最多被覆盖k次。每个区间有一个价值w,一个区间只能被选择一次。问如何选择使得权值最大。

自己的题解:【COGS743】最长k可重区间集问题 最大权不相交路径

简单来说,首先发现:如果把连续选的互不相交的区间看做一条路径,那么问题便为取k次的最大权不相交路径问题。

对于每一次,有两种方法:

1.将每个区间看做一个点,拆点表示权值。然后将其与左端点在其右端点之后的区间连边,表示可以组成一条路径。源点向每个区间连边表示是路径起始,每个区间向汇点连边表示是路径终点。然后限制流量为k。然后最大费用最大流。

2.离散化后将数轴上每个点看做一个点。第i个点向第i+1个点连边表示传递流量。对于一个区间,左端点向右端点连边表示覆盖一次,加费用为边权。跑最大费用最大流。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;

int head[510],nxt[SZ],tot = 1;

struct edge{
    int f,t;
    LL d,c;
}l[SZ];

void build(int f,int t,LL d,LL c)
{
    l[++ tot].t = t;
    l[tot].d = d;
    l[tot].f = f;
    l[tot].c = c;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,LL d,LL c)
{
    build(f,t,d,c); build(t,f,0,-c);
}

LL dist[510];
deque<int> q;
int pre[510],use[SZ];

bool spfa(int s,int e)
{
    memset(dist,63,sizeof(dist));
    memset(pre,0,sizeof(pre));

    dist[s] = 0;
    use[s] = 1;
    q.push_front(s);
    while(q.size())
    {
        int u = q.front(); q.pop_front();
        use[u] = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(l[i].d && dist[v] > dist[u] + l[i].c)
            {
                dist[v] = dist[u] + l[i].c;
                pre[v] = i;
                if(!use[v])
                {
                    use[v] = 1;
                    if(q.empty()) q.push_front(v);
                    else if(dist[q.front()] > dist[v])
                        q.push_front(v);
                    else
                        q.push_back(v);
                }
            }
        }
    }
    return dist[e] < -INF ? false : true;
}

LL dfs(int s,int e)
{
    LL x = INF,ans = 0;
    for(int i = pre[e];i;i = pre[l[i].f])
        x = min(x,l[i].d);
    for(int i = pre[e];i;i = pre[l[i].f])
        ans += x * l[i].c,l[i].d -= x,l[i ^ 1].d += x;
    return ans;
}

LL ek(int s,int e)
{
    LL ans = 0;
    while(spfa(s,e))
    {
        int tmp = dfs(s,e);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}


struct qj
{
    int x,y,w;
}ll[SZ];


int lsh[SZ];

int main()
{
    int T = read(),k;
    while(T --)
    {
        memset(head,0,sizeof(head)); tot = 1;
        lsh[0] = 0;
        scanf("%d%d",&n,&k);
        for(int i = 1;i <= n;i ++)
        {
            int x = read(),y = read(),w = read();
            lsh[++ lsh[0]] = x; lsh[++ lsh[0]] = y;
            ll[i] = (qj){x,y,w};
        }
        sort(lsh + 1,lsh + 1 + lsh[0]);
        int len = unique(lsh + 1,lsh + 1 + lsh[0]) - lsh - 1;
        for(int i = 1;i <= n;i ++)
        {
            ll[i].x = lower_bound(lsh + 1,lsh + 1 + len,ll[i].x) - lsh;
            ll[i].y = lower_bound(lsh + 1,lsh + 1 + len,ll[i].y) - lsh;
            insert(ll[i].x,ll[i].y,1,-ll[i].w);
        }
        for(int i = 1;i <= len - 1;i ++)
            insert(i,i + 1,INF,0);
        int s = len + 1,e = len + 2;
        insert(s,1,k,0); insert(len,e,k,0);
        printf("%d\n",-ek(s,e));
    }
    return 0;
}


E : hdu - 6118

给一张图,每个点可以以ai的价格最多购买bi个商品,可以以ci的价格卖出最多di个商品。在边上每单位距离运输一个商品需要花费为1。问调动物品使其获得最大的价值是多少。

将商品看做流量,那么bi和di就成了流量限制,ai和bi还有边权就成了费用。由于运输没有限制,所以流量设为INF。然后跑一遍费用流就行了。

我的EK竟然T成狗,百度之星的时候改了一万遍,这个题也改了一万遍,最后还是搞了个zkw费用流才过…………

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;

typedef long long LL;
const int INF = 1000000010;
const int SZ = 1000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m;

int head[510],nxt[SZ],tot = 1;

struct edge{
    int f,t;
    LL d,c;
}l[SZ];

void build(int f,int t,LL d,LL c)
{
    l[++ tot].t = t;
    l[tot].d = d;
    l[tot].f = f;
    l[tot].c = c;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,LL d,LL c)
{
    build(f,t,d,c); build(t,f,0,-c);
}

LL dist[510],ans = 0;
queue<int> q;
int pre[SZ],mark[510],s,e;

bool spfa()
{
    memset(mark,0,sizeof(mark));
    memset(dist,-1,sizeof(dist));
    q.push(e); mark[e] = 1,dist[e] = 0;
    while(q.size())
    {
        int u = q.front(); q.pop();
        mark[u] = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(l[i ^ 1].d && dist[u] + l[i ^ 1].c > dist[v])
            {
                dist[v] = dist[u] + l[i ^ 1].c;
                if(!mark[v])
                    mark[v] = 1,q.push(v);
            }
        }
    }
    return dist[s] != -1;
}
LL dfs(int x,LL f)
{
    mark[x] = 1;
    if(x == e) return f;
    LL w,used = 0;
    for(int i = head[x];i;i = nxt[i])
    {
        int v = l[i].t;
        if(dist[v] == dist[x] - l[i].c && l[i].d && !mark[v])
        {
            w = f - used;
            w = dfs(v,min(w,l[i].d));
            ans += w * l[i].c;
            l[i].d -= w;l[i ^ 1].d += w;
            used += w; if(used == f) return f;
        }
    }
    return used;
}
void zkw()
{
    while(spfa())
    {
        memset(mark,0,sizeof(mark));
        mark[e] = 1;
        while(mark[e])
        {
            mark[e] = 0;
        //    puts("233");
            dfs(s,INF);
        }
    }
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,0,sizeof(head)); tot = 1;
        s = n + 1,e = n + 2;
        for(int i = 1;i <= n;i ++)
        {
            int a = read(),b = read(),c = read(),d = read();
            insert(s,i,b,-a); insert(i,e,d,c);
        }
        for(int i = 1;i <= m;i ++)
        {
            int x = read(),y = read(),z = read();
            insert(x,y,INF,-z); insert(y,x,INF,-z);
        }
        ans = 0;
        zkw();
        printf("%lld\n",ans);
    }
    return 0;
}


F : poj - 3281

每个奶牛喜欢有一个喜欢的爱吃的东西集合和爱喝的东西集合。每个吃的和喝得只有一个。问最多有多少个奶牛可以吃到自己喜欢吃的和喜欢喝的。

把奶牛拆点,流量为1,防止他多吃多喝。然后就成sb题了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 410;
const int INF = 1000000010;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;

struct edge{
    int t,d;
}l[1000010];

void build(int f,int t,int d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,int d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

int dfs(int u,int flow)
{
    if(u == e || flow == 0) return flow;
    int rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            int f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        int tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}


int main()
{
    int n = read(),n1 = read(),n2 = read();
    s = 2 * n + n1 + n2 + 1;
    e = 2 * n + n1 + n2 + 2;
    for(int i = 1;i <= n;i ++)
    {
        int k1 = read(),k2 = read();
        insert(i,i + n,1);
        while(k1 --)
            insert(read() + 2 * n,i,1);
        while(k2 --)
            insert(i + n,2 * n + n1 + read(),1);
    }
    for(int i = 1;i <= n1;i ++)
        insert(s,i + 2 * n,1);
    for(int i = 1;i <= n2;i ++)
        insert(i + 2 * n + n1,e,1);
    printf("%d\n",dinic());
    return 0;
}


G : hdu - 3061

最大权闭合图问题。

闭合图:图中任何点可以到达的点一定在闭合图中。

建模:s向权为wi的正权点连边为wi,权为wi的负权点向e连边为-wi。原图中的边流量为INF。

我们称割上每条边都与源点或汇点关联的割为简单割

首先发现,对于一个最小割,其一定为简单割。

设S为割割开的包含源点的点集,E为包含汇点的点集。上标的正负号表示点权为正/负的点集

简单割和闭合图一一对应:对于被割分开的S点集,若存在一点的后继在T点集,则说明存在一条容量为INF的边在割上,即不为简单割。

所以S点集即为一个闭合图。

由于最小割为简单割,所以最小割的权值$C=\sum_{w_i \in T^{+}}w_i+\sum_{wi \in S^{-}}(-w_i)$。

对于一个闭合图,其权值为$W=\sum_{w_i \in S^+}w_i-\sum_{w_i \in S^-}(-w_i)$。

两式相加得:$W+C=\sum_{w_i \in T^{+}}w_i+\sum_{w_i \in S^+}w_i=\sum_{w_i \in V^+}w_i$

即点权为正的权值和。

这样最小化C,就能最大化W了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 510;
const int INF = 1000000010;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;

bool isin(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

struct edge{
    int t,d;
}l[1000010];

void build(int f,int t,int d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,int d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

int dfs(int u,int flow)
{
    if(u == e || flow == 0) return flow;
    int rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            int f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        int tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,0,sizeof(head)); tot = 1;
        s = n + 1,e = n + 2;
        int sum = 0;
        for(int i = 1;i <= n;i ++)
        {
            int x = read();
            if(x < 0) insert(i,e,-x);
            if(x > 0) insert(s,i,x),sum += x;
        }
        for(int i = 1;i <= m;i ++)
        {
            int x = read(),y = read();
            insert(x,y,INF);
        }
        printf("%d\n",sum - dinic());
    }
    return 0;
}


H : hdu - 3657

给一个n*m的方格,指定其中k个方格必选。可以选择任意方格,选择后得到这个方格的权值。但若选择两个相邻方格则有2*(x&y)的损失。问最大权值。

可以发现就是B题多加了两个条件。

对于必选点:将其与源点或者汇点的边权设为INF,防割。因为割掉表示不选。

对于选两个的损失:之前把相邻点设为INF是因为要保证两个点不能同时被选。这时可以将INF变为2*(x&y)表示损失。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 10010;
const int INF = 1000000010;
const int mod = 1000000007;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m;
int head[SZ],nxt[1000010],tot = 1,s,e;

bool isin(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

struct edge{
    int t,d;
}l[1000010];

void build(int f,int t,int d)
{
    l[++ tot].t = t;
    l[tot].d = d;
    nxt[tot] = head[f];
    head[f] = tot;
}

void insert(int f,int t,int d)
{
    build(f,t,d); build(t,f,0);
}

queue<int> q;

int deep[SZ];

bool bfs()
{
    memset(deep,0,sizeof(deep));
    while(q.size()) q.pop();
    deep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int f = q.front(); q.pop();
        for(int i = head[f];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!deep[v] && l[i].d)
            {
                deep[v] = deep[f] + 1,q.push(v);
                if(v == e) return true;
            }
        }
    }
    if(deep[e]) return true;
    return false;
}

int dfs(int u,int flow)
{
    if(u == e || flow == 0) return flow;
    int rest = flow;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(deep[v] == deep[u] + 1 && l[i].d)
        {
            int f = dfs(v,min(rest,l[i].d));
            if(f > 0)
            {
                rest -= f;
                l[i].d -= f;
                l[i ^ 1].d += f;
                if(!rest) break;
            }
            else deep[v] = 0;
        }
    }
    if(flow - rest == 0) deep[u] = 0;
    return flow - rest;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        int tmp = dfs(s,INF);
        if(tmp == 0) break;
        ans += tmp;
    }
    return ans;
}

int get_id(int x,int y)
{
    return (x - 1) * m + y;
}
int a[110][110];
bool use[110][110];

int main()
{
    int k;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(use,0,sizeof(use));
        int sum = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                a[i][j] = read();
        for(int i = 1;i <= k;i ++)
        {
            int x = read(),y = read();
            use[x][y] = 1;
        }
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                int x = a[i][j];
                sum += x;
                if(!((i + j) & 1))
                    for(int k = 0;k < 4;k ++)
                    {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if(isin(x,y))
                            insert(get_id(i,j),get_id(x,y),2 * (a[i][j] & a[x][y]));
                    }
            }
        s = n * m * 2 + 1,e = s + 1;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                int x = use[i][j] ? INF : a[i][j];
                if(!((i + j) & 1))
                    insert(s,get_id(i,j),x);
                else
                    insert(get_id(i,j),e,x);
            }
        printf("%d\n",sum - dinic());
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法网络流图论模拟赛
最后由DQS修改于2017-08-16 20:52
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆