首页 > 搜索 > DFS搜索 > HDU 4494-Teamwork -网络流-[解题报告]HOJ
2015
07-17

HDU 4494-Teamwork -网络流-[解题报告]HOJ

Teamwork

问题描述 :

Some locations in city A has been destroyed in the fierce battle. So the government decides to send some workers to repair these locations. There are m kinds of workers that were trained for different skills. Each location need some number of some kinds of workers and has a schedule that at what time can the repair begins, and the time cost of repair. Any job cannot begin until all the workers required arrived.
For example, location 1 needs 2 workers of type 1 and 3 workers of type 2, and the beginning time and time cost is 100 minute and 90 minute correspondingly, then 5 workers that satisfy the requirement should arrive before 100 minute, start working at 100 minute and get the job done at 190 minute. Notice that two different types of workers cannot replace each other, so with 3 workers of type 1 and only 2 workers of type 2, this job cannot be done.
Workers can go from one location to another after their jobs are done. You can take the Euclidean distance between locations as the time workers need to travel between them. Each worker should be sent from a depot initially at 0 minute. Now your task is to determine the minimum number of workers needed to be sent from depot so that all the jobs can be done.

输入:

There are multiple test cases, the integer on the first line T (T<25) indicates the number of test cases.
Each test case begins with two integers n (<=150), the number of location(including the depot) and m(<=5), the number of different skills.
The next line gives two integers x0, y0 indicates the coordinate of depot.
Then follows n – 1 lines begins with 4 integer numbers: xi, yi, bi(bi>0), pi(pi>0), (xi, yi) gives the coordinate of the i-th location, bi gives the beginning time and pi gives the time cost. The rest of the line gives m non-negative integers v1, v2, …, vm, of which the i-th number indicates the the number of workers of type i needed (for all vi, 0<=vi<10, each location at least requires one worker).
All integers are less than 1000000 (106).

输出:

There are multiple test cases, the integer on the first line T (T<25) indicates the number of test cases.
Each test case begins with two integers n (<=150), the number of location(including the depot) and m(<=5), the number of different skills.
The next line gives two integers x0, y0 indicates the coordinate of depot.
Then follows n – 1 lines begins with 4 integer numbers: xi, yi, bi(bi>0), pi(pi>0), (xi, yi) gives the coordinate of the i-th location, bi gives the beginning time and pi gives the time cost. The rest of the line gives m non-negative integers v1, v2, …, vm, of which the i-th number indicates the the number of workers of type i needed (for all vi, 0<=vi<10, each location at least requires one worker).
All integers are less than 1000000 (106).

样例输入:

2 
4 1 
0 0 
0 1 1 1 3 
1 1 3 3 4 
1 0 10 1 5 
4 1 
0 0 
0 1 1 1 3 
1 1 3 3 4 
1 0 3 1 5 

样例输出:

5
9

网上比较多的代码都是用费用流做的,但是这个题目简单的描述就是求最小路径覆盖,每个点覆盖的次数不是1了而已。简单修改求最小路径覆盖的方法即可,源点向顶点,顶点向汇点连的边都变成点需要被覆盖的次数即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=15e1+9,inf=1e9;
int n,m;
int sum[maxn][10];
long long dist[maxn][maxn],x[maxn],y[maxn],st[maxn],ed[maxn];
int level[maxn<<1],que[maxn<<1];
int head[maxn<<1],lon;
struct
{
    int next,to,c;
}e[maxn*maxn<<2];
void edgeini()
{
    memset(head,-1,sizeof(head));
    lon=-1;
}
void edgemake(int from,int to,int c)
{
    e[++lon].c=c;
    e[lon].to=to;
    e[lon].next=head[from];
    head[from]=lon;
}
void make(int from,int to,int c)
{
    edgemake(from,to,c);
    edgemake(to,from,0);
}

bool makelevel(int s,int t)
{
    memset(level,0,sizeof(level));
    int front=1,end=0;
    que[++end]=s;
    level[s]=1;
    while(front<=end)
    {
        int u=que[front++];
        if(u==t) return true;
        for(int k=head[u];k!=-1;k=e[k].next)
        {
            int v=e[k].to;
            if(!level[v]&&e[k].c)
            {
                que[++end]=v;
                level[v]=level[u]+1;
            }
        }
    }
    return false;
}

int dfs(int now,int t,int maxf)
{
    if(now==t) return maxf;
    int ret=0;
    for(int k=head[now];k!=-1;k=e[k].next)
    {
        int u=e[k].to;
        if(level[u]==level[now]+1&&e[k].c)
        {
            int f=dfs(u,t,min(e[k].c,maxf-ret));
            e[k].c-=f;
            e[k^1].c+=f;
            ret+=f;
            if(ret==maxf) return ret;
        }
    }
    return ret;
}

int maxflow(int s,int t)
{
    int ret=0;
    while(makelevel(s,t))
    {
        ret+=dfs(s,t,inf);
    }
    return ret;
}


void getdist()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        dist[i][j]=(x[i]-x[j])*(x[i]-x[j]);
        dist[i][j]+=(y[i]-y[j])*(y[i]-y[j]);
    }
}

void makegraph(int tt)
{
    edgeini();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j)
    {
        if(st[j]>=ed[i])
        {
            long long tmp=(st[j]-ed[i])*(st[j]-ed[i]);
            if(tmp>=dist[i][j])
            {
                make(i,j+n,inf);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        make(0,i,sum[i][tt]);
        make(i+n,n+n+1,sum[i][tt]);
    }
}

int main()
{
//    freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int ans=0;
        scanf("%d%d",&n,&m);
        scanf("%d%d",&x[1],&y[1]);
        n--;
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d %I64d %I64d %I64d",&x[i],&y[i],&st[i],&ed[i]);
            ed[i]+=st[i];
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&sum[i][j]);
                ans+=sum[i][j];
            }
        }
        getdist();
        for(int i=1;i<=m;i++)
        {
            makegraph(i);
            ans-=maxflow(0,n+n+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

参考:http://blog.csdn.net/yrleep/article/details/13391427