先求出最短路径,然后用最短路径上的边构建一个新图,在新图上求最小割。
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int const N= 1010, M= 200010;
int n, m;
int const inf= 0x7fffffff;
int res;
struct Node{
Node(){}
Node(int a,int b ):adj(a), wt(b) {}
int adj, wt; };
struct cmp{
bool operator()( Node a, Node b ){
return a.wt> b.wt; }
};
vector<Node> mata[N], matb[N];
int S, T;
int dista[N], distb[N];
int dijks( int s, int t, int d[], vector<Node> mat[] ){
for( int i= 0; i<= n; ++i ) d[i]= inf;
d[s]= 0;
priority_queue<Node, vector<Node>, cmp> que;
que.push( Node( s, 0 ) );
while( !que.empty() ){
int u= que.top().adj, w= que.top().wt; que.pop();
if( w!= d[u] ) continue;
for( size_t i= 0; i< mat[u].size(); ++i ){
int v= mat[u][i].adj, t= mat[u][i].wt;
if( d[u]+ t< d[v] ){
d[v]= d[u]+ t;
que.push( Node( v, d[v] ) );
}
}
}
return d[t];
}
struct Edge{
int flow, adj;
Edge* next;
}tb[M];
Edge* mat[N], *Pre[N];
int cnt= -1;
inline Edge* reserve( Edge* p ){
return tb+ ( (p- tb)^ 1 );
}
inline void add( int u, int v, int c ){
++cnt;
tb[cnt].adj= v; tb[cnt].flow= c;
tb[cnt].next= mat[u]; mat[u]= tb+ cnt;
++cnt;
tb[cnt].adj= u; tb[cnt].flow= 0;
tb[cnt].next= mat[v]; mat[v]= tb+ cnt;
}
int que[M], ht[N], flag[N], path[N], head, tail;
int bfs(){
que[0]= S; head= 0; tail= 0;
for( int i= 0; i<= n; ++i ) ht[i]= -1; ht[S]= 0;
while( head<= tail ){
int u= que[head++];
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== -1 && p->flow ){
ht[p->adj]= ht[u]+ 1;
que[++tail]= p->adj;
}
}
return ht[T]!= -1;
}
int dfs( int u, int flow ){
if( u== T ) return flow;
int tf= 0, f;
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== ht[u]+ 1 && p->flow && flow> tf &&
( f= dfs( p->adj, min( p->flow, flow- tf ) ) ) ){
reserve( p )->flow+= f;
p->flow-= f;
tf+= f;
}
if( tf== 0 ) ht[u]= -1;
return tf;
}
void build(){
cnt= -1;
for( int i= 0; i<= n; ++i ) mat[i]= 0;
for( int u= 1; u<= n; ++u )
for( size_t i= 0; i< mata[u].size(); ++i ){
int v= mata[u][i].adj, w= mata[u][i].wt;
if( dista[u]+ w+ distb[v]== res ){
add( u, v, 1 );
}
}
}
int main(){
int test;
scanf("%d",&test );
while( test-- ){
scanf("%d%d",&n,&m );
for( int i= 0; i< m; ++i){
int u, v, d;
scanf("%d%d%d", &u, &v, &d );
mata[u].push_back( Node(v,d) );
matb[v].push_back( Node(u,d) );
}
scanf("%d%d", &S, &T );
dijks( S, T, dista, mata );
res= dijks( T, S, distb, matb );
build();
int ans= 0;
while( bfs() ) ans+= dfs( S, 0x7fffffff );
printf("%d\n", ans );
for( int i= 0; i<= n; ++i )
mata[i].clear(), matb[i].clear();
}
return 0;
}
分享到:
相关推荐
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu杭电网络编程结课报告 聊天室
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类