2015
07-16

# 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

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

（因为点的访问是要按照顺序的），然后从原点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;
}

{
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].v = u;
edge[idx].w = 0;
edge[idx].c = -c;
return;
}

void make(int lim)
{
memset(bj,-1,sizeof(bj));
s = idx = 0;
ss = 2*n+1;
t = 2*n+2;
for(int i=1;i<=n;i++)
{
if(map[0][i] < inf)
{
}
for(int j=i+1;j<=n;j++)
{
if(map[i][j] < inf)
{
}
}
}
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;
{
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();
}