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 100015using 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];}}}elseif( u != s ){lev[u] = INT_MAX;u = pre[u];}elsebreak;}}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;                  把这里注释掉就水过了，比赛时各种TLEnode[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;}