问题描述 :
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
const int oo=1e9;
const int mm=11111111;
const int mn=888888;
int node,src,dest,edge;
int ver[mm],flow[mm],cost[mm],nex[mm];
int head[mn],dis[mn],p[mn],q[mn],vis[mn];
/**这些变量基本与最大流相同，增加了
cost 表示边的费用，
p 记录可行流上节点对应的反向边
*/
void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0; i<node; i++)head[i]=-1,vis[i]=0;
edge=0;
}
void addedge(int u,int v,int f,int c)
{
ver[edge]=v,flow[edge]=f,cost[edge]=c,nex[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,cost[edge]=-c,nex[edge]=head[v],head[v]=edge++;
}
/**以上同最大流*/
/**spfa 求最短路，并用 p 记录最短路上的边*/
bool spfa()
{
int i,u,v,l,r=0,tmp;
for(i=0; i<node; ++i)dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for(l=0; l!=r; (++l>=mn)?l=0:l)
for(i=head[u=q[l]],vis[u]=0; i>=0; i=nex[i])
if(flow[i]&&dis[v=ver[i]]>(tmp=dis[u]+cost[i]))
{
dis[v]=tmp;
p[v]=i^1;
if(vis[v]) continue;
vis[q[r++]=v]=1;
if(r>=mn)r=0;
}
return p[dest]>-1;
}
/**源点到汇点的一条最短路即可行流，不断的找这样的可行流*/
int SpfaFlow()
{
int i,ret=0,delta;
while(spfa())
{
for(i=p[dest],delta=oo; i>=0; i=p[ver[i]])
if(flow[i^1]<delta)delta=flow[i^1];
for(i=p[dest]; i>=0; i=p[ver[i]])
flow[i]+=delta,flow[i^1]-=delta;
ret+=delta*dis[dest];
}
return ret;
}
int tu[110][110];
void floyd(int n)
{
for(int k=0; k<=n; k++)
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
tu[i][j]=min(tu[i][j],tu[i][k]+tu[k][j]);
}
int main()
{
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k)&&n+m+k)
{
int st=2*n+1,ed=2*n+2;
prepare(2*n+3,st,ed);
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
tu[i][j]=i==j?0:oo;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c<tu[a][b])
tu[a][b]=tu[b][a]=c;
}
floyd(n);
addedge(st,0,k,0);
addedge(0,ed,k,0);
for(int i=1; i<=n; i++)
addedge(0,i,1,tu[0][i]),addedge(i,i+n,1,-100000),addedge(i+n,ed,1,tu[i][0]);
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
addedge(i+n,j,1,tu[i][j]);
printf("%d\n",SpfaFlow()+100000*n);
}
return 0;
}
#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;
}