首页 > 代码库 > HDU 4971 A simple brute force problem.(最小割，最大权闭合图)

HDU 4971 A simple brute force problem.(最小割，最大权闭合图)

2024-07-19 00:41:58   226人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4971

A simple brute force problem.Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 182    Accepted Submission(s): 115


Problem Description
There‘s a company with several projects to be done. Finish a project will get you profits. However, there are some technical problems for some specific projects. To solve the problem, the manager will train his employee which may cost his budget. There may be dependencies between technical problems, for example, A requires B means you need to solve problem B before solving problem A. If A requires B and B requires A, it means that you should solve them at the same time. You can select which problems to be solved and how to solve them freely before finish your projects. Can you tell me the maximum profit?
 

Input
The first line of the input is a single integer T(<=100) which is the number of test cases. 

Each test case contains a line with two integer n(<=20) and m(<=50) which is the number of project to select to complete and the number of technical problem.

Then a line with n integers. The i-th integer(<=1000) means the profit of complete the i-th project.

Then a line with m integers. The i-th integer(<=1000) means the cost of training to solve the i-th technical problem.

Then n lines. Each line contains some integers. The first integer k is the number of technical problems, followed by k integers implying the technical problems need to solve for the i-th project.

After that, there are m lines with each line contains m integers. If the i-th row of the j-th column is 1, it means that you need to solve the i-th problem before solve the j-th problem. Otherwise the i-th row of the j-th column is 0.
 

Output
For each test case, please output a line which is "Case #X: Y ", X means the number of the test case and Y means the the maximum profit.
 

Sample Input
4
2 3
10 10
6 6 6
2 0 1
2 1 2
0 1 0
1 0 0
0 0 0
2 3
10 10
8 10 6
1 0
1 2
0 1 0
1 0 0
0 0 0
2 3
10 10
8 10 6
1 0
1 2
0 1 0
0 0 0
0 0 0
2 3
10 10
8 10 6
1 0
1 2
0 0 0
1 0 0
0 0 0
 

Sample Output
Case #1: 2
Case #2: 4
Case #3: 4
Case #4: 6
 

Source
2014 Multi-University Training Contest 10
 


题意：

给出n个项目，m个问题，完成某个项目需要解决一些问题，解决某个问题可能要先解决另一个问题，比如问题i依赖于问题j，那要先解决j再解决i，如果互相依赖，则要同时解决。完成某个项目会获得收益，解决某个问题需要一些花费，求最大净收益。

分析：

一点开题就感觉是个网络流，不过一直没想到该怎么建图，后来队友切了签到题发现这题其他队过得有点快，就感觉应该是个乱搞的搜索(当然，乱搜确实能过)，后来看到一道做过的网络流就很高兴地去切了，切完后我又想了下这题，发现就是个最大权闭合图，幸好以前做过一道，并且还记得建图的方法，于是在刚过的网络流的代码上改了两下就AC了。

建图方法：项目是正权点，权值为收益，问题为负权点，权值为花费。项目对所要解决的问题连边，容量为INF;增加源点，连向正权点，容量为收益;增加汇点，负权点向其连边，容量为花费。最大权和为正权和减去上图中的最小割。


#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define itn int
#define maxn 1007
#define maxm 2333333
#define INF 0x3f3f3f3f
using namespace std;


int a[maxn],b[maxn];
int fir[maxn];
itn u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;
itn q[maxn<<2];

itn lv[maxn],iter[maxn];

void add_edge(int _u,int _v,int _w)
{

    int e=e_max++;
    u[e]=_u;v[e]=_v;cap[e]=_w;
    nex[e]=fir[u[e]];fir[u[e]]=e;
    e=e_max++;
    u[e]=_v;v[e]=_u;cap[e]=0;
    nex[e]=fir[u[e]];fir[u[e]]=e;
}

void dinic_bfs(itn s)
{
    int f,r;
    lv[s]=0;
    q[f=r=0]=s;

    while (f<=r)
    {
        int x=q[f++];
        for (int e=fir[x];~e;e=nex[e])
        {
            if (cap[e]>flow[e] && lv[v[e]]<0)
            {
                lv[v[e]]=lv[u[e]]+1;
                q[++r]=v[e];
            }
        }
    }
}

int dinic_dfs(int s,int t,int _f)
{
    if (s==t)   return _f;

    for (int &e=iter[s];~e;e=nex[e])
    {
        if (cap[e]>flow[e] && lv[s]<lv[v[e]])
        {
            int _d=dinic_dfs(v[e],t,min(cap[e]-flow[e],_f));
            if (_d>0)
            {
                flow[e]+=_d;
                flow[e^1]-=_d;
                return _d;
            }
        }
    }

    return 0;
}


itn max_flow(int s,int t)
{
    int total_flow=0;

    memset(flow,0,sizeof flow);
    for (;;)
    {
        memset(lv,-1,sizeof lv);
        dinic_bfs(s);

        if (lv[t]==-1)  break;

        memcpy(iter,fir,sizeof fir);

        itn _f=0;
        while ((_f=dinic_dfs(s,t,INF))>0)
            total_flow+=_f;

    }

    return total_flow;

}

int main()
{
    int n,m;
    itn T_T,cas=0;
    scanf("%d",&T_T);

    while(T_T--)
    {
        printf("Case #%d: ",++cas);
        scanf("%d%d",&n,&m);
        itn s=0,t=n+m+1;
        itn sr=0,sc=0;
        e_max=0;
        memset(fir,-1,sizeof fir);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            add_edge(s,i,a[i]);
            sr+=a[i];
        }

        for (int i=1;i<=m;i++)
        {
            scanf("%d",b+i);
            add_edge(i+n,t,b[i]);
        }

        for (int i=1,k,p;i<=n;i++)
        {
            scanf("%d",&k);
            for (int j=0;j<k;j++)
            {
                scanf("%d",&p);
                p++;
                add_edge(i,p+n,INF);
            }

        }

        int x;
        for (int i=1;i<=m;i++)
        {
            for (int j=1;j<=m;j++)
            {
                scanf("%d",&x);
                if (x)
                add_edge(i+n,j+n,INF);
            }
        }

        int res=sr-max_flow(s,t);
        
        printf("%d\n",res);
    }


    return 0;
}


HDU 4971 A simple brute force problem.(最小割，最大权闭合图)


联系
我们