Problem Description
The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads, and each road has the same length and connects two towns. The town numbered 1 is where general’s castle is located, and the town numbered N is where the enemies are staying. The general supposes that the enemies would choose a shortest path. He knows his army is not ready to fight and he needs more time. Consequently he decides to put some barricades on some roads to slow down his enemies. Now, he asks you to find a way to set these barricades to make sure the enemies would meet at least one of them. Moreover, the barricade on the i-th road requires wi units of wood. Because of lacking resources, you need to use as less wood as possible.
Input
The first line of input contains an integer t, then t test cases follow.
For each test case, in the first line there are two integers N(N≤1000) and M(M≤10000).
The i-the line of the next M lines describes the i-th edge with three integers u,v and w where 0≤w≤1000 denoting an edge between u and v of barricade cost w.
Output
For each test cases, output the minimum wood cost.
Sample Input
1
4 4
1 2 1
2 4 2
3 1 3
4 3 4
Sample Output
4
題目鏈接：HDU⑸889
題目大意：給出n個(gè)點(diǎn)，m條路徑，每條路徑長(zhǎng)度為1，敵人從m點(diǎn)攻擊1點(diǎn)，敵人總是選擇最短路徑來(lái)進(jìn)攻我方，為了禁止敵人，我們要把1些路封死，每條路徑封死需要1些花費(fèi)，求最小花費(fèi)。
題目思路：首先用spfa處理出最短路中的邊，然后做1遍最大流求出最小割。
可參考HDU⑶416
以下是代碼:
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>
using namespace std;
#define LL long long
#define MAXN 1005
struct node
{
int v,len,w; //終點(diǎn)、長(zhǎng)度
node(int a,int b,int c){
v = a,len = b,w = c;
}
};
struct edge
{
int to,cap,rev;
edge(int a,int b,int c){
to = a,cap = b,rev = c;
}
};
int n;
vector <node> g[MAXN];
vector <edge> G[MAXN];
int d[MAXN];
bool used[MAXN];//DFS中用到的訪問(wèn)標(biāo)記
void addEdge(int u,int v,int cap)
{
G[u].push_back(edge(v,cap,G[v].size()));
G[v].push_back(edge(u,0,G[u].size()-1));
}
//通過(guò)DFS尋到增廣路
int dfs(int v,int t,int f){
if(v == t)
return f;
used[v] = true;
for(int i = 0; i < G[v].size(); i++){
edge &e = G[v][i];
if(!used[e.to] && e.cap > 0){
int d = dfs(e.to,t,min(f,e.cap));
if(d > 0){
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
//求解從s到t的最大流
int max_flow(int s,int t){
int flow = 0;
while(1){
memset(used,false,sizeof(used));
int f = dfs(s,t,99999999);
if(f == 0)
return flow;
flow += f;
}
}
void solve()
{
for (int i = 1; i <= n; i++)
{
int len = g[i].size();
for (int j = 0; j < len; j++)
{
int v = g[i][j].v;
int l = g[i][j].len;
int w = g[i][j].w;
if (d[v] - d[i] == l) //判斷是不是為最短路
{
addEdge(i,v,w);
}
}
}
}
void SPFA(int x) //x為出發(fā)點(diǎn)
{
int v[MAXN];
memset(v,0,sizeof(v));
queue<int>q;
q.push(x);
v[x] = 1;d[x] = 0;
while(!q.empty())
{
int nod = q.front();
q.pop();
v[nod] = 0;
for(int i = 0;i < g[nod].size();i++)
{
int nxtnod = g[nod][i].v;
if(d[nxtnod] > d[nod] + g[nod][i].len)
{
d[nxtnod] = d[nod] + g[nod][i].len;
if(!v[nxtnod])
{
v[nxtnod] = 1;
q.push(nxtnod);
}
}
}
}
}
void init()
{
memset(d,1,sizeof(d));
for (int i = 0; i < MAXN-1; i++)
{
g[i].clear();
G[i].clear();
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
int m;
cin >> n >> m;
init();
for (int i = 0; i < m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(node(v,1,w));
g[v].push_back(node(u,1,w));
}
SPFA(1);
solve();
long long ans = max_flow(1,n);
printf("%lld\n",ans);
}
return 0;
}
上一篇 Android開發(fā)筆記（一百二十六）自定義音樂(lè)播放器
下一篇 【框架整合】Maven-SpringMVC3.X+Spring3.X+MyBatis3-日志、JSON解析、表關(guān)聯(lián)查詢等均已配置好
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
