首页 > ACM题库 > HDU-杭电 > HDU 4411-Arrest-最短路径-[解题报告]HOJ
2015
07-16

HDU 4411-Arrest-最短路径-[解题报告]HOJ

Arrest

问题描述 :

There are (N+1) cities on TAT island. City 0 is where police headquarter located. The economy of other cities numbered from 1 to N ruined these years because they are all controlled by mafia. The police plan to catch all the mafia gangs in these N cities all over the year, and they want to succeed in a single mission. They figure out that every city except city 0 lives a mafia gang, and these gangs have a simple urgent message network: if the gang in city i (i>1) is captured, it will send an urgent message to the gang in city i-1 and the gang in city i -1 will get the message immediately.
The mission must be carried out very carefully. Once a gang received an urgent message, the mission will be claimed failed.
You are given the map of TAT island which is an undirected graph. The node on the graph represents a city, and the weighted edge represents a road between two cities(the weight means the length). Police headquarter has sent k squads to arrest all the mafia gangs in the rest N cities. When a squad passes a city, it can choose to arrest the gang in the city or to do nothing. These squads should return to city 0 after the arrest mission.
You should ensure the mission to be successful, and then minimize the total length of these squads traveled.

输入:

There are multiple test cases.
Each test case begins with a line with three integers N, M and k, here M is the number of roads among N+1 cities. Then, there are M lines. Each of these lines contains three integers X, Y, Len, which represents a Len kilometer road between city X and city Y. Those cities including city 0 are connected.
The input is ended by “0 0 0”.
Restrictions: 1 ≤ N ≤ 100, 1 ≤ M ≤ 4000, 1 ≤ k ≤ 25, 0 ≤ Len ≤ 1000

输出:

There are multiple test cases.
Each test case begins with a line with three integers N, M and k, here M is the number of roads among N+1 cities. Then, there are M lines. Each of these lines contains three integers X, Y, Len, which represents a Len kilometer road between city X and city Y. Those cities including city 0 are connected.
The input is ended by “0 0 0”.
Restrictions: 1 ≤ N ≤ 100, 1 ≤ M ≤ 4000, 1 ≤ k ≤ 25, 0 ≤ Len ≤ 1000

样例输入:

3 4 2
0 1 3
0 2 4
1 3 2
2 3 2
0 0 0

样例输出:

14

题意:有n(0<=n<=100)个点m(0<=m<=4000)条边的无向图,有k(0<=k<=25)个人从0点出发,依次占领1~n点,因为 i 被占领的时候会通知

          i – 1 点,到达一个点的时候可以选择不占领,问最后<=k个人占领所有地方再走回来的最小值。

题解:floyd之后建图,因为要保证所有的点依次占领,所以每个点拆点流量为1费用为-inf(保证所有点都被占领),然后从j(j < i)建边到 i 流量为inf,费用为map[ j ][ i ]

        (因为点的访问是要按照顺序的),然后从原点ss到i建容量为inf费用为map[0][i]的边,同理从i+n(i 拆的出边点)到t建容量为inf费用为map[i][0]的边,枚举k后,

         重新建图,建s到ss容量为看,费用为0的边跑费用流即可。


Sure原创,转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
using namespace std;
const int inf = 100010;
const int maxn = 102;
const int maxe = 20000;
const int maxm = 28;
struct node
{
    int v,w,c;
    int next;
}edge[maxe << 1];
int head[maxn << 1],dis[maxn << 1],pre[maxn << 1],bj[maxn << 1];
int map[maxn][maxn];
bool vis[maxn << 1];
queue <int> Q;
int m,n,k,idx,s,ss,t;

void init()
{
    for(int i=0;i<=n;i++)
    {
        map[i][i] = 0;
        for(int j=0;j<=n;j++)
        {
            map[i][j] = map[j][i] = inf;
        }
    }
    return;
}

void read()
{
    int u,v,w;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        if(map[u][v] > w)
        {
            map[u][v] = map[v][u] = w;
        }
    }
    return;
}

void floyd()
{
    for(int k=0;k<=n;k++)
    {
        for(int i=0;i<=n;i++)
        {
            if(i == k || map[i][k] == inf) continue;
            for(int j=0;j<=n;j++)
            {
                if(j == i || j == k || map[k][j] == inf) continue;
                if(map[i][k] + map[k][j] < map[i][j])
                {
                    map[i][j] = map[i][k] + map[k][j];
                    map[j][i] = map[i][j];
                }
            }
        }
    }
    return;
}

void addedge(int u,int v,int w,int c)
{
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].c = c;
    edge[idx].next = head[u];
    head[u] = idx++;

    edge[idx].v = u;
    edge[idx].w = 0;
    edge[idx].c = -c;
    edge[idx].next = head[v];
    head[v] = idx++;
    return;
}

void make(int lim)
{
    memset(head,-1,sizeof(head));
    memset(bj,-1,sizeof(bj));
    s = idx = 0;
    ss = 2*n+1;
    t = 2*n+2;
    addedge(s,ss,lim,0);
    for(int i=1;i<=n;i++)
    {
        if(map[0][i] < inf)
        {
            addedge(ss,i,inf,map[0][i]);
            addedge(i+n,t,inf,map[i][0]);
        }
        addedge(i,i+n,1,-inf);
        for(int j=i+1;j<=n;j++)
        {
            if(map[i][j] < inf)
            {
                addedge(i+n,j,inf,map[i][j]);
            }
        }
    }
    return;
}

bool spfa(int st)
{
    memset(vis,false,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    while(!Q.empty())
    {
        Q.pop();
    }
    for(int i=0;i<=t;i++)
    {
        dis[i] = (i == st) ? 0 : inf;
    }
    Q.push(st);
    vis[st] = true;
    while(!Q.empty())
    {
        int cur = Q.front();
        Q.pop();
        vis[cur] = false;
        for(int i=head[cur];i != -1;i=edge[i].next)
        {
            if(edge[i].w > 0 && dis[edge[i].v] > dis[cur] + edge[i].c)
            {
                dis[edge[i].v] = dis[cur] + edge[i].c;
                pre[edge[i].v] = i;
                if(vis[edge[i].v] == false)
                {
                    vis[edge[i].v] = true;
                    Q.push(edge[i].v);
                }
            }
        }
    }
    return dis[t] < inf;
}

void solve()
{
    int res = inf;
    for(int i=1;i<=k;i++)
    {
        make(i);
        int ans = 0;
        while(spfa(s))
        {
            int dx = inf;
            int top = t;
            while(top != s)
            {
                dx = MIN(dx , edge[pre[top]].w);
                top = edge[pre[top]^1].v;
            }
            top = t;
            while(top != s)
            {
                ans += dx * edge[pre[top]].c;
                edge[pre[top]].w -= dx;
                edge[pre[top]^1].w += dx;
                top = edge[pre[top]^1].v;
            }
        }
        res = MIN(res , ans + n * inf);
    }
    printf("%d\n",res);
    return;
}

int main()
{
    while(scanf("%d %d %d",&n,&m,&k) && n+m+k)
    {
        init();
        read();
        floyd();
        solve();
    }
    return 0;
}

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

参考:http://blog.csdn.net/flying_stones_sure/article/details/8010155