专栏首页饶文津的专栏【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)

【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)

Less Time, More profit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

The city planners plan to build N plants in the city which has M shops. Each shop needs products from some plants to make profit of proi units.Building ith plant needs investment of payi units and it takes ti days.Two or more plants can be built simultaneously, so that the time for building multiple plants is maximum of their periods(ti).You should make a plan to make profit of at least L units in the shortest period.InputFirst line contains T, a number of test cases.For each test case, there are three integers N, M, L described above.And there are N lines and each line contains two integers payiti(1<= i <= N).Last there are M lines and for each line, first integer is proi, and there is an integer k and next k integers are index of plants which can produce material to make profit for the shop. 1 <= T <= 30 1 <= N, M <= 200

1≤L,ti≤1000000000
1≤payi,proi≤30000

 Output

For each test case, first line contains a line “Case #x: t p”, x is the number of the case, t is the shortest period and p is maximum profit in t hours. You should minimize t first and then maximize p. If this plan is impossible, you should print “Case #x: impossible”

Sample Input

2

1 1 2

1 5

3 1 1

1 1 3

1 5

3 1 1

Sample Output

Case #1: 5 2

Case #2: impossible

 Author

金策工业综合大学(DPRK)

Source

2016 Multi-University Training Contest 9

 M个商店,N个工厂,每个商店获利的条件是建设了指定的k个工厂。求总获利不小于L,工厂建设的时间最大值最小是多少。

 工厂到汇点建一条边pay[i],源点到商店建一条边pro[i],商店到需要的工厂建一条边INF,商店的总收益-最小割就是答案。

可以看看国家集训队论文:Amber《最小割模型在信息学竞赛中的应用》

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 205<<1
#define sf(a) scanf("%d",&a);
using namespace std;
const int INF=0x3f3f3f3f;
struct plant{
    int pay,t,id;
}pt[N];
struct shop{
    int pro,k,pt[N],t;
}s[N];
int t,n,m,l,st,ed,tot;
int arc[N][N], d[N];
int ans,tans;
bool bfs()
{
    memset(d, -1, sizeof d);
    queue<int>q;
    q.push(st);
    d[st] = 0;
    while(!q.empty())
    {
        int i,k=q.front();
        q.pop();
        for(i = 1; i <= ed; i++)
            if(arc[k][i] > 0 && d[i] == -1)
            {
                d[i] = d[k] + 1;
                q.push(i);
            }
    }
    return d[ed]>0;
}
int dinic (int k, int low)
{
    if(k == ed)return low;
    int a,i;
    for(i = 1; i <= ed; i++)
        if(d[i] == d[k] + 1&&  arc[k][i] > 0 &&(a = dinic(i, min(low, arc[k][i]))))
        {
            arc[k][i] -= a;
            arc[i][k] += a;
            return a;
        }
    return 0;
}
int cmp(plant a,plant b){
    return a.t<b.t;
}
int main() {
    sf(t);
    for(int cas=1;cas<=t;cas++){
        printf("Case #%d: ",cas);
        scanf("%d%d%d",&n,&m,&l);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&pt[i].pay,&pt[i].t);
            pt[i].id=i;
        }
        for(int i=1;i<=m;i++){
            sf(s[i].pro);
            sf(s[i].k);
            s[i].t=0;
            for(int j=1;j<=s[i].k;j++){
                int x;
                sf(x);
                s[i].pt[j]=x;
                s[i].t=max(s[i].t,pt[x].t);
            }
        }
        sort(pt+1,pt+1+n,cmp);
        int ok=0;
        st=n+m+1,ed=st+1;
        for(int i=1;i<=n;i++){
            memset(arc,0,sizeof arc);
            for(int j=1;j<=i;j++)
                arc[pt[j].id][ed]=pt[j].pay;
            tot=0;
            for(int j=1;j<=m;j++)if(s[j].t<=pt[i].t){
                tot+=s[j].pro;
                arc[st][j+n]=s[j].pro;
                for(int k=1;k<=s[j].k;k++)
                arc[j+n][s[j].pt[k]]=INF;
            }
            ans = 0;
            while(bfs())
                while(tans=dinic(st, INF)) ans += tans;
            ans=tot-ans;
            if(ans>=l){
                printf("%d %d\n",pt[i].t,ans);
                ok=1;
                break;
            }
        }
        if(!ok)puts("impossible");
    }
}

工厂按时间排序再依次增大最大时间,这样是140ms,改成二分以为会更快,结果960ms,去了注释们再交一次居然超时了。可能是dinic用的是邻接矩阵的原因。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU 4305】Lightning(生成树计数)

    There are N robots standing on the ground (Don't know why. Don't know how). 

    饶文津
  • 【HDU 5833】Zhu and 772002(异或方程组高斯消元)

    比如12=2^2*3,对应的奇偶值为01(2的个数是偶数为0,3的个数是奇数为1),3的对应奇偶值为01,于是12*3是完全平方数。

    饶文津
  • 【USACO 2.1】Ordered Fractions

    饶文津
  • 数独终盘生成的几种方法

    为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

    孟君
  • LeetCode 135 Candy

    ShenduCC
  • 1009 产生数 2002年NOIP全国联赛普及组

    009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

    attack
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack

扫码关注云+社区

领取腾讯云代金券