Less Time, More profit 最大权闭合子图（最大流最小割）

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 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 1≤payi,proi≤30000
OutputFor 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

Sample Output

Case #1: 5 2
Case #2: impossible

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 405
#define L 31
#define INF 1000000009
#define eps 0.00000001
#define sf(a) scanf("%lld",&a)
struct plant
{
    LL pay, time;
    LL id;
    bool operator<(const plant& rhs) const
    {
        return time < rhs.time;
    }
};
struct shop
{
    LL cnt, time, pro;
    LL pl[MAXN];
};
shop s[MAXN];
plant p[MAXN];
LL g[MAXN << 1][MAXN << 1];
LL level[MAXN<<1];
LL T, n, m, l, st, ed, ans, tmp;
bool bfs()
{
    memset(level, -1, sizeof(level));
    level[st] = 0;
    queue<LL> q;
    q.push(st);
    while (!q.empty())
    {
        LL f = q.front();
        q.pop();
        for (LL i = 1; i <= ed; i++)
        {
            if (level[i] == -1 && g[f][i] > 0)
            {
                level[i] = level[f] + 1;
                q.push(i);
            }
        }
    }
    return level[ed] > 0;
}
LL dinic(LL k, LL low)
{
    if (k == ed)return low;
    LL a;
    for (LL i = 1; i <= ed; i++)
    {
        if (level[i] == level[k] + 1 && g[k][i] > 0 && (a = dinic(i, min(low, g[k][i]))))
        {
            g[k][i] -= a;
            g[i][k] += a;
            return a;
        }
    }
    return 0;
}
void solve()
{
    ans = 0;
    while (bfs())
    {
        while (tmp = dinic(st, INF))
            ans += tmp;
    }
}
int main()
{
    sf(T);
    for (LL cas = 1; cas <= T; cas++)
    {
        sf(n), sf(m), sf(l);
        for (LL i = 1; i <= n; i++)
        {
            sf(p[i].pay), sf(p[i].time);
            p[i].id = i;
        }
        for (LL i = 1; i <= m; i++)
        {
            sf(s[i].pro);
            sf(s[i].cnt);
            s[i].time = 0;
            for (LL j = 0; j < s[i].cnt; j++)
            {
                sf(s[i].pl[j]);
                s[i].time = max(s[i].time, p[s[i].pl[j]].time);
            }
        }
        sort(p + 1, p + 1 + n);
        bool f = false;
        st = n + m + 1, ed = st + 1;
        printf("Case #%lld: ", cas);
        for (LL i = 1; i <= n; i++)
        {
            memset(g, 0, sizeof(g));
            for (LL j = 1; j <= i; j++)
                g[p[j].id][ed] = p[j].pay;
            LL tot = 0;
            for (LL j = 1; j <= m; j++)
            {
                if (s[j].time <= p[i].time)
                {
                    tot += s[j].pro;
                    g[st][j + n] = s[j].pro;
                    for (LL k = 0; k < s[j].cnt; k++)
                        g[j + n][s[j].pl[k]] = INF;
                }
            }
            solve();
            ans = tot - ans;
            if (ans >= l)
            {
                printf("%lld %lld
", p[i].time, ans);
                f = true;
                break;
            }
        }
        if (!f)
            printf("impossible
");
    }
}

Less Time, More profit 最大权闭合子图（最大流最小割）

相关推荐