首页 > ACM题库 > HDU-杭电 > HDU 4037-Development Value-图-[解题报告]HOJ
2015
04-16

HDU 4037-Development Value-图-[解题报告]HOJ

Development Value

问题描述 :

StarCraft 2 (SC2) is a famous game. More and more people fall in love with this game.

As a crazy fan of SC2, Ahua (flower fairy) play it day and night. Recently, he found that the most important part of being a top player of SC2 is economic development, which means you should get as much mine as possible by training SCVs (space construction vehicle) to collect mine. Train a SCV at ith second costs Ci units of mine. After training, this SCV can collect Di units of mine each second. Training a SCV needs one second of time.

Based on that, he composes a formula to evaluate the development in a time span from xth second to yth second. Assume at xth second, Ahua has no SCV and mine. He trains one SCV at each second during xth second and yth second (the mount of mine can be negative, so that he always can train SCV). Each SCV will collect some amount of mines for Ahua in each second after it was trained. At ith second Ahua has Mi units of mine in total. The development value is defined as sum(Mi) (x ≤ i ≤ y). Now he asks you to help him calculate the development value. To make it more interesting, Ahua can apply following operations:

Cost x y z: the cost of training a SCV between xth second to yth second will increase by z units of mine. i.e. Ci for x ≤ i ≤ y will increase by z.

Collect x y z: each SCV trained between xth second and yth second can collect z more mines every second after it has been trained. i.e. Di for x ≤ i ≤ y will increase by z.

Query x y: output the development value between xth second and yth second.

输入:

First line of the input is a single integer T (T ≤ 10), indicates there are T test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100000), means the maximum time you should deal with.

Following N lines, each contain two integers Ci and Di (0 ≤ Ci, Di ≤ 100000), the cost and collect speed of SCV training in ith second initially as described above.

The next line is an integer Q (1 ≤ Q ≤ 10000), the number of operations you should deal with. Then Q lines followed, each line will be “Cost x y z”, "Collect x y z” or “Query x y”.
1 ≤ x ≤ y ≤ N, 0 ≤ z ≤ 100000

输出:

First line of the input is a single integer T (T ≤ 10), indicates there are T test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100000), means the maximum time you should deal with.

Following N lines, each contain two integers Ci and Di (0 ≤ Ci, Di ≤ 100000), the cost and collect speed of SCV training in ith second initially as described above.

The next line is an integer Q (1 ≤ Q ≤ 10000), the number of operations you should deal with. Then Q lines followed, each line will be “Cost x y z”, "Collect x y z” or “Query x y”.
1 ≤ x ≤ y ≤ N, 0 ≤ z ≤ 100000

样例输入:

1
5
1 3
2 3
3 1
2 2
3 3
5
Query 1 3
Cost 2 2 1
Query 1 3
Collect 1 1 5
Query 1 3

样例输出:

Case 1:
2
0
15

题意:给定一个n*n(n<=1000)的B矩阵和1*n的C矩阵,现在想找到合适的1*n的A矩阵,使得D = (A * B – C) * AT的值最大。

题解:化简得到
Development Value
Development Value

第一项是定值,题目转换为要最小化后面的三项之和,抽象到最小割模型求解。
建图,令源为s,汇为t,中间有n个点。点i到j有一条容量为B[i][j]的边,同时s到点i有一条容量为C[i]的边,点i到t有一条容量为sum{j}B[i][j]的边。
这样,图的任意一个割就与一个A一一对应,最小割即为最小的后面三项之和。简单解释下任意一个割与一个A一一对应:

首先明确后三项即为在B矩阵中所有sigma Bij(A[i] == 0 || A[j] == 0),所以对于任意一点i,s – i (A[i] == 1)或者i – t(A[i] == 0)必选其中之一,如果A[i] == 1则对于所有j(A[j]== 0)来说,存在s – j – i – t的增广路,所以j– i就一定要包含在该割内,对应即为B[j][i],所以任意一个割与一个A一一对应。

Sure原创,转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int inf = 1 << 29;
const int maxn = 1010;
const int maxe = 2100000;
struct node
{
    int v,w;
    int next;
}edge[maxe];
int head[maxn],cur[maxn],dis[maxn],gap[maxn],pre[maxn];
int B[maxn][maxn],C[maxn],D[maxn];
int n,s,t,idx,sum;

void init()
{
    memset(head,-1,sizeof(head));
    memset(D,0,sizeof(D));
    scanf("%d",&n);
    s = idx = sum = 0;
    t = n + 1;
    return;
}

void addedge(int u,int v,int w)
{
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].next = head[u];
    head[u] = idx++;

    edge[idx].v = u;
    edge[idx].w = 0;
    edge[idx].next = head[v];
    head[v] = idx++;
    return;
}

void read()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&B[i][j]);
            D[j] += B[i][j];
            if(i != j) addedge(i,j,B[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&C[i]);
        addedge(s,i,C[i]);
        addedge(i,t,D[i]);
        sum += D[i];
    }
    return;
}

int isap(int N)
{
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    for(int i=0;i<N;i++)
    {
        cur[i] = head[i];
    }
    int i,top = s;
    int maxflow = 0,flow = inf;
    gap[s] = N;
    while(dis[s] < N)
    {
        for(i=cur[top];i != -1;i=edge[i].next)
        {
            if(edge[i].w > 0 && dis[top] == dis[edge[i].v] + 1)
            {
                break;
            }
        }
        if(i != -1)
        {
            cur[top] = i;
            if(edge[i].w < flow)
            {
                flow = edge[i].w;
            }
            top = edge[i].v;
            pre[top] = i;
            if(top == t)
            {
                maxflow += flow;
                while(top != s)
                {
                    edge[pre[top]].w -= flow;
                    edge[pre[top]^1].w += flow;
                    top = edge[pre[top]^1].v;
                }
                flow = inf;
            }
        }
        else
        {
            if(--gap[dis[top]] == 0)
            {
                break;
            }
            cur[top] = head[top];
            dis[top] = N;
            for(int j=head[top];j != -1;j=edge[j].next)
            {
                if(edge[j].w > 0 && dis[top] > dis[edge[j].v] + 1)
                {
                    cur[top] = j;
                    dis[top] = dis[edge[j].v] + 1;
                }
            }
            gap[dis[top]]++;
            if(top != s)
            {
                top = edge[pre[top]^1].v;
            }
        }
    }
    return maxflow;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        init();
        read();
        printf("%d\n",sum - isap(t+1));
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/flying_stones_sure/article/details/7943555


,
  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。