HDU5889 Barricade(最短路)(网络流)
2024-08-24 17:15:35
Barricade
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 604 Accepted Submission(s): 172
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.
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.
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
4 4
1 2 1
2 4 2
3 1 3
4 3 4
Sample Output
4
【分析】给你一个无向图,现有敌人要从n点走到1点且他只走最短路(每条路长度一样)。为了阻止敌人到达1点,要求在某些路上设置障碍,使得敌人最少能遇到一个障碍。
其实就是在最短路上跑网络流,因为最小割就是最大流。一开始一直超时,后来问的学长才知道我的Dinic板子有问题,没有当前弧优化,然后改了一下,就过了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 10000
typedef long long ll;
using namespace std;
const int N=;
const int M=;
struct Node
{
int v,w;
Node(int vv,int ww):v(vv),w(ww){};
};
vector<Node>e[N];
int s,t,n,m,vs,vt;
int d[N];
int vis[N];
void spfa()
{
memset(vis,,sizeof(vis));
for(int i = ;i<=n;i++)
d[i]=inf;
d[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u]=;
for(int i = ;i<e[u].size();i++)
{
int v = e[u][i].v;
if(d[v]>d[u]+)
{
d[v]=d[u]+;
if(!vis[v])
q.push(v);
vis[v]=;
}
}
}
} struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct Dinic
{
int s,t;
vector<Edge>edges;
vector<int> G[N];
bool vis[N];
int d[N];
int cur[N];
void init()
{
for (int i=;i<=n+;i++)
G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,));
edges.push_back(Edge(to,from,,));
int mm=edges.size();
G[from].push_back(mm-);
G[to].push_back(mm-);
}
bool BFS()
{
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
d[s]=;
vis[s]=;
while (!q.empty())
{
int x = q.front();q.pop();
for (int i = ;i<G[x].size();i++)
{
Edge &e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow)
{
vis[e.to]=;
d[e.to] = d[x]+;
q.push(e.to);
}
}
}
return vis[t];
} int DFS(int x,int a)
{
if (x==t || a==)
return a;
int flow = ,f;
for(int &i=cur[x];i<G[x].size();i++)
{
Edge &e = edges[G[x][i]];
if (d[x]+ == d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>)
{
e.flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if (a==)
break;
}
}
return flow;
} int Maxflow(int s,int t)
{
this->s=s;
this->t=t;
int flow = ;
while (BFS())
{
memset(cur,,sizeof(cur));
flow+=DFS(s,inf);
}
return flow;
}
}dc; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++)
e[i].clear();
for(int i = ;i<=m;i++)
{
int u,v,di;
scanf("%d%d%d",&u,&v,&di);
e[u].push_back(Node(v,di));
e[v].push_back(Node(u,di));
}
s=,t=n;
spfa();
dc.init();
for(int i = ;i<=n;i++)
for(int j = ;j<e[i].size();j++)
if(d[e[i][j].v]==d[i]+)
dc.AddEdge(i,e[i][j].v,e[i][j].w);
printf("%d\n",dc.Maxflow(s,t));
}
}
最新文章
- 探秘Tomcat——连接篇
- jQuery CSS操作及jQuery的盒子模型
- iOS集成ijkplayer视频直播框架,遇到的bug和坑...
- C++和C#混合编程
- 【Fate/kaleid liner 魔法少女☆伊莉雅】系列中实践的、新世代的动画摄影工作流
- ip的正则表达式 完美版
- maven-使用assembly自定义打包
- CodeForces Round #278 (Div.2) (待续)
- select/**/*/**/from/**/RegSite
- MySQL plugin结构
- win10系统搭建虚拟机:VMware Workstation Player 12环境+Ubuntu Kylin 16.04 LTS系统
- H5 可堆叠的圆环进度条,支持任意数量子进度条
- java基础语法(三大基础)
- java 基础 ----- Arrays 工具类
- WPS Office手机版调用接口代码指导帖之二 [复制链接]
- format()函数用法
- 聊聊 CAS
- Java MyBatis insert数据库数据后返回主键
- 基于C++11实现的线程池
- Java基础教程(6)--数组