HDU 3599 War (dinic + dijkstra +heap )

HDU 3599 War

类似于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;
}