2012天津市赛区网络赛 hdu 4280 Island Transport

2012天津赛区网络赛 hdu 4280 Island Transport

这题比赛时套各种模板都TLE到吐了。。。赛后发现自己2B了，按照以前的模板的写法，每次都是由u->v, v->u各构成一条边，这里的话本来是无向图每次构建从u->v的就行了，汗。。。。不过效率还是很低啊，模板还不够强大，因为也有人构双边sap水过的。。。

当然赛后别人说是平面图构图最短路 

http://www.mzry1992.com/blog/miao/9.html

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <limits.h>
#define MAX 100015
using namespace std;
int n,np,nc,m;
int lev[MAX];
typedef struct NODE{
	int from,to;
	int cap;
	int next;
}NODE;

struct cor
{
    int x,y,idx;
}cord[MAX];
bool cmp(const cor&a,const cor&b)
{
    return a.x<b.x;
}
NODE node[MAX<<2];
int cou,net[MAX];
int a[MAX];
int pos[MAX],pre[MAX];
void init()
{
	cou = 2;
	memset(node,'/0',sizeof(node));
	memset(net,-1,sizeof(net));
}
queue<int> q;
int BFS(int s,int t)
{
	int u,v,head,cap;
	memset(lev,-1,sizeof(lev));
	q.push(s);
	lev[s] = 0;
	while( !q.empty() )
	{
		u = q.front();
		q.pop();
		head = net[u];
		while( head != -1 )
		{
			v = node[head].to;
			cap = node[head].cap;
			if( cap > 0 && lev[v] == -1 )
			{
				lev[v] = lev[u] + 1;
				q.push(v);
			}
			head = node[head].next;
		}
	}
	return lev[t] != -1;
}

int Dinic(int s,int t)
{

	int flow = 0;
	int head,cap;
	int i,u,flag,v,ag,k;
	while( BFS(s,t) )
	{
		for(i=0; i<=t; i++)
			a[i] = INT_MAX;
		u = s;
		while(1)
		{
			flag = 0;
			head = net[u];
			while( head != -1 )
			{
				cap = node[head].cap;
				v = node[head].to;
				if( cap > 0 && lev[u] + 1 == lev[v] )
				{
					pos[v] = head;
					flag = 1;
					break;
				}
				head = node[head].next;
			}
			if( flag )
			{
				pre[v] = u;
				a[v] = cap;
				if( a[v] > a[u] )
					a[v] = a[u];
				u = v;
				if( u == t )
				{
					ag = a[t];
					flow += ag;
					for(v=t; v!=s; v=pre[v])
					{
						node[pos[v]^1].cap += ag;
						node[pos[v]].cap -= ag;
						a[v] -= ag;
						if( node[pos[v]].cap == 0 )
							u = pre[v];
					}
				}
			}
			else
				if( u != s )
				{
					lev[u] = INT_MAX;
					u = pre[u];
				}
				else
					break;
		}
	}
	return flow;
}
void Add(int u,int v,int len)
{
	node[cou].from = u;
	node[cou].to = v;
	node[cou].cap = len;
	node[cou].next = net[u];
	net[u] = cou++;

	/*node[cou].from = v;                  把这里注释掉就水过了，比赛时各种TLE
	node[cou].to = u;
	node[cou].cap = 0;
	node[cou].next = net[v];
	net[v] = cou++;*/
}


int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{

	    init();
	    int n,m;
	    scanf("%d%d",&n,&m);
	    int _min=1000001,_max=-1000001;
	    int min_id,max_id;
	    for(int i=1;i<=n;i++)
	    {
	        scanf("%d%d",&cord[i].x,&cord[i].y);
	        cord[i].idx=i;
	        if(cord[i].x<_min) {_min=cord[i].x; min_id=i;}
	        if(cord[i].x>_max) {_max=cord[i].x; max_id=i;}
	    }
      
	    for(int i=1;i<=m;i++)
	    {
	        int s,t,c;
	        scanf("%d%d%d",&s,&t,&c);
	        Add(s,t,c);
	        Add(t,s,c);
	    }
	    Add(0,min_id,INT_MAX);
	    Add(max_id,n+1,INT_MAX);
	    int ans=Dinic(0,n+1);
	    cout<<ans<<endl;


	}


return 0;
}