Less Time, More profit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1453    Accepted Submission(s): 199

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.
 

Input
First 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 payi, ti(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
 

题意：给出n个工厂，m个商店，商店需要k个固定的工厂提供商品，每个工厂可以为多家商店提供。建工厂需要时间和钱，但可以同时建。商店可以赚钱，问净利润大于L的最少时间

做法：仔细一想时间那个条件就是用来枚举的，而不是用来加边权的啊。顺着这个思路想，有木有觉得最大权闭合图 hdu 3879 Base Station 有模板！跟这个题有点像啊，这何止是有点像啊，就是一样的嘛……

再说说最大权闭合图：闭合图是指满足点集所有出边入边都在这个团里面。最大权闭合图是指总点权最大的闭合图。最大权闭合图的权值=左侧边的和-最小割，画个图就明白了




假设紫色圈出来的是最大权闭合图，那么它的权值等于1+2-5-6.最小割等于3+4+5+6.左侧边权和等于1+2+3+4.

#include <stdio.h>
#include<cstring>
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int oo=0x3f3f3f3f;
const int mm=9000000;
const int mn=9000000;
int node ,scr,dest,edge;
int ver[mm],flow[mm],Next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _scr,int _dest)
{
    node=_node,scr=_scr,dest=_dest;
    for(int i=0; i<node; ++i)
        head[i]=-1;
    edge=0;
}
void addedge(int u,int v,int c)
{
    ver[edge]=v,flow[edge]=c,Next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=0,Next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; i++)
        dis[i]=-1;
    dis[q[r++]=scr]=0;
    for(l=0; l<r; ++l)
    {
        for(i=head[u=q[l]]; i>=0; i=Next[i])
        {
            if(flow[i]&&dis[v=ver[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)
                    return 1;
            }
        }
    }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)
        return exp;
    for(int &i=work[u],v,tmp; i>=0; i=Next[i])
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0; i<node; i++)
            work[i]=head[i];
        while(delta=Dinic_dfs(scr,oo))
            ret+=delta;
    }
    return ret;
}
int plantcost[300],planttime[300],profits[300];
int tmp[300];
vector<int>shop[300];
bool vis1[300],vis[300];
int n,m,l,ans1,ans2;
int main()
{
   // freopen("cin.txt","r",stdin);
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&l);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&plantcost[i],&planttime[i]);
            tmp[i]=planttime[i];
        }
        for(int i=0;i<=201;i++)shop[i].clear();
        for(int i=1;i<=m;i++)
        {
            int xx;
            scanf("%d%d",&profits[i],&xx);
            for(int j=0;j<xx;j++)
            {
                int x;
                scanf("%d",&x);
                shop[i].push_back(x);
            }
        }
        sort(tmp+1,tmp+n+1);
        bool flag=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            memset(vis1,0,sizeof(vis1));
            for(int j=1;j<=n;j++)
                if(planttime[j]<=tmp[i])
                    vis[j]=1;
            prepare(n+m+2,0,n+m+1);
            int sum=0;
            for(int j=1;j<=m;j++)//shop
            {
                bool exi=1;
                for(int k=0;k<shop[j].size();k++)
                    if(vis[shop[j][k]]==0)exi=0;
                if(exi)
                {
                    addedge(0,j,profits[j]);
                    sum+=profits[j];
                    for(int k=0;k<shop[j].size();k++)
                    {
                        int x=shop[j][k];
                        addedge(j,x+m,oo);
                        if(vis1[x]==0)
                        {
                            addedge(x+m,n+m+1,plantcost[x]);
                            vis1[x]=1;
                        }
                    }
                }
            }
            int ans=Dinic_flow();
            if(sum-ans>=l)
            {
                flag=1;
                ans1=tmp[i];
                ans2=sum-ans;
                break;
            }
        }
        printf("Case #%d: ",cas++);
        if(!flag)printf("impossible\n");
        else printf("%d %d\n",ans1,ans2);
    }
    return 0;
}