类似于zoj2760 how many shortest paths,需要求出有多少个互不相交的最短路条数,需要求出最短路,然后让满足d[to] == d[from] + w[from][to] 的两个点间连接一条弧,容量为1,然后再S,T之间求最大流即可,本题难度 不大,就是出数据的人该遭鄙视,边的顶点竟然有为0的,害得我搞了好长时间,求最短路的时候可以用spfa和dij+heap,速度差不多,哎,好久么有写最短路了,我这个代码写了好几遍,我感觉已经写的非常规范了,可以当做模板用。。。
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #define MAX 1501 #define INF 999999999 using namespace std; class Arc{ public: int to,w; Arc *next,*anti; Arc *ass( int tt,int ww,Arc *&b ){ to=tt;w=ww;next=b;b=this;return this; } }a[ 100000 ]; class po{ public: int to,len; }; po makepo( int to,int len ){ po t;t.to=to;t.len=len;return t;} bool operator < (po a,po b ) { return a.len > b.len; } Arc *biao[ MAX ],*tu[ MAX ]; int d[ MAX ],S,T,N,countt; Arc* addedge( int from,int to,int w,Arc **biao ){ return a[ countt++ ].ass( to, w, biao[from] ); } void add( int from,int to,int w,Arc **biao ){ Arc *p1 = addedge(from,to,w,biao); Arc *p2 = addedge(to,from,0,biao); p1->anti = p2; p2->anti = p1; } void DIJ( void ){ int i,flag[ MAX ],now = S; priority_queue<po> q; fill( d, d+MAX, INF ); fill( flag, flag+MAX, 0 ); d[ now ] = 0; flag[ now ] = 1; for( i = 1; i < N; i ++ ){ for( Arc *p=biao[now]; p != NULL; p = p->next ) if( !flag[ p->to] && d[ p->to] > d[ now] + p->w ){ d[ p->to ] = d[ now ] + p->w; q.push( makepo(p->to,d[p->to]) ); } if( q.empty() ) break; now = q.top().to;q.pop(); flag[ now ] = 1; } } void construct( void ){ for( int i = 1; i <= N; i++ ) for( Arc *p=biao[i]; p != NULL; p = p->next ) if( d[ p->to ] == d[i] + p->w ) add( i, p->to, 1, tu ); } int bfs( void ){ queue<int> q; fill( d,d+MAX,-1); d[S] = 0; q.push( S ); while( !q.empty() ){ int u = q.front();q.pop(); for( Arc *p = tu[u]; p != NULL; p = p->next ){ if( d[ p->to ] == -1 && p->w > 0 ) d[ p->to ] = d[u] + 1,q.push( p->to ); } } return d[T] != -1; } int dinic( int u,int sum ){ int f,o; if( u == T ) return sum; o = sum; for( Arc *p = tu[u]; p != NULL && sum; p = p->next ) if( d[p->to] == d[u] + 1 && p->w >0 ){ f = dinic( p->to, min( p->w,sum) ); p->w -= f; p->anti->w += f; sum -= f; } return o - sum; } int main( void ){ int from,to,w; int i,j,k,cases; scanf("%d",&cases); while( cases-- ){ countt = 0; scanf("%d",&N); S = 1;T = N; for( i = 1; i <= N; i++ ) biao[i] = tu[i] = NULL; while( scanf("%d%d%d",&from,&to,&w) ){ if( !from && !to && !w ) break; if( !from || !to ) continue; addedge( from, to, w, biao ); addedge( to, from, w, biao ); } DIJ(); if( N == 1 || d[ T ] == INF ){ printf("0\n"); continue; } construct(); int total = 0; while( bfs() ) total += dinic( S, INF ); printf("%d\n",total ); } return 0; }