HDU-4280-Island Transport（最大流+dinic+向前星（优化||当前弧优化））

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280

Problem Description

　　In the vast waters far far away, there are many islands. People are living on the islands, and all the transport among the islands relies on the ships.
　　You have a transportation company there. Some routes are opened for passengers. Each route is a straight line connecting two different islands, and it is bidirectional. Within an hour, a route can transport a certain number of passengers in one direction. For safety, no two routes are cross or overlap and no routes will pass an island except the departing island and the arriving island. Each island can be treated as a point on the XY plane coordinate system. X coordinate increase from west to east, and Y coordinate increase from south to north.
　　The transport capacity is important to you. Suppose many passengers depart from the westernmost island and would like to arrive at the easternmost island, the maximum number of passengers arrive at the latter within every hour is the transport capacity. Please calculate it.

Input

　　The first line contains one integer T (1<=T<=20), the number of test cases.
　　Then T test cases follow. The first line of each test case contains two integers N and M (2<=N,M<=100000), the number of islands and the number of routes. Islands are number from 1 to N.
　　Then N lines follow. Each line contain two integers, the X and Y coordinate of an island. The K-th line in the N lines describes the island K. The absolute values of all the coordinates are no more than 100000.
　　Then M lines follow. Each line contains three integers I1, I2 (1<=I1,I2<=N) and C (1<=C<=10000) . It means there is a route connecting island I1 and island I2, and it can transport C passengers in one direction within an hour.
　　It is guaranteed that the routes obey the rules described above. There is only one island is westernmost and only one island is easternmost. No two islands would have the same coordinates. Each island can go to any other island by the routes.

Output

　　For each test case, output an integer in one line, the transport capacity.

Sample Input

5 7

3 3

3 0

3 1

0 0

4 5

1 3 3

2 3 4

2 4 3

1 5 6

4 5 3

1 4 4

3 4 2

6 7

-1 -1

0 1

0 2

1 0

1 1

2 3

1 2 1

2 3 6

4 5 5

5 6 3

1 4 6

2 5 5

3 6 4

Sample Output

题目大意：给出T组数据，每组数据给出一个n，一个m表示有n个小岛，m条路，输入n个小岛的坐标，在输入m条路的起点，终点，运载人数；

求出最西边到最东边最多能运多少人；

上面给出的坐标不用太在意，只要找到x最小和x最大的那个坐标就是起点，终点，然后注意是双向图，存图的时候向前星两边都要存，裸的的最大流，没什么好说的，注意清空就行了：

这是一个超辣鸡的代码，只能擦边9900ms++过，下面的那个只用5000ms+就行了

ac：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 998244353
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
struct node{
    int v,w,nxt;
    node(int _v=0,int _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[100005<<1];
int head[100005];
int dis[100005];
int n,m;
int e,s,t;

void add(int u,int v,int w)
{
    edge[e]=node(v,w,head[u]);
    head[u]=e++;
    
    edge[e]=node(u,w,head[v]);
    head[v]=e++;
}

bool bfs()
{
    clean(dis,-1);
    dis[s]=0;
    queue<int> que;
    que.push(s);
    while(que.size())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i!=-1;i=edge[i].nxt)
        {
        	int temp=edge[i].v;
            if(dis[temp]==-1&&edge[i].w>0)
            {
                dis[temp]=dis[u]+1;
                que.push(temp);
            }
        }
    }
    //cout<<dis[t]<<endl;
    return dis[t]>-1;
}

int dfs(int u,int low)
{
    if(u==t)
        return low;
    int res=0;
    for(int i=head[u];i!=-1;i=edge[i].nxt)//遍历邻接表 
    {
    	int temp=edge[i].v;
        if(edge[i].w&&dis[temp]==dis[u]+1)
        {
        	int f=dfs(temp,min(low-res,edge[i].w));
        	edge[i].w-=f;
        	edge[i^1].w+=f;
        	res+=f;
        	if(res==low)
        		break;
		}
    }
//    cout<<res<<endl;
    if(!res)//最小值等于0，说明这条路不通 
    	dis[u]=-2;
    return res;
}

void max_flow()
{
    int ans=0,res;
    while(bfs())
    {
        while((res=dfs(s,INF))>0)
            ans=ans+res;
    }
    cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
    	e=0;
        clean(head,-1);
        clean(edge,0);
        cin>>n>>m;
        int s1=INF,t1=-INF;
        int x1,y1;
        for(int i=1;i<=n;++i)
        {
            cin>>x1>>y1;
            if(x1<s1)
                s1=x1,s=i;
            if(x1>t1)
                t1=x1,t=i;
        }
        int a,b,l;
        for(int i=1;i<=m;++i)
        {
            cin>>a>>b>>l;
            add(a,b,l);
        }
        max_flow();
    }
    return 0;
}

还有一个就是用当前弧优化+多路增广，也是板子。注意要用scanf（）；不然可能会超时（不确定）

其中dfs中的循环用了&i=cur[u]，改变的是i这个变量地址中的参数，下次引用i的这个变量的时候直接改变了是更新过的i

ac：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 998244353
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
struct node{
    int v,w,nxt;
    node(int _v=0,int _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[100005<<1];
int head[100005],cur[100005];
int dis[100005];
int n,m;
int e,s,t;

void add(int u,int v,int w)
{
    edge[e]=node(v,w,head[u]);
    head[u]=e++;
    
    edge[e]=node(u,w,head[v]);
    head[v]=e++;
}

bool bfs()
{
	clean(dis,-1);
    dis[t]=0;
    queue<int> que;
    que.push(t);
    while(que.size())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i+1;i=edge[i].nxt)
        {
        	int temp=edge[i].v;
            if(dis[temp]==-1&&edge[i^1].w>0)
            {
                dis[temp]=dis[u]+1;
                que.push(temp);
            }
        }
    }
    //cout<<dis[s]<<endl;
    return dis[s]!=-1;
}

int dfs(int u,int low)
{
	//cout<<u<<endl;
    if(u==t)
        return low;
    int res=low;
    for(int &i=cur[u];i+1;i=edge[i].nxt)//遍历邻接表 
    {//这里&是取地址符
    	int temp=edge[i].v,d;
		if(dis[u]==dis[temp]+1&&edge[i].w/*&&(d=dfs(temp,min(res,edge[i].w)))>0*/)
        {
        	int d=dfs(temp,min(res,edge[i].w));
        	edge[i].w-=d;
        	edge[i^1].w+=d;
        	res-=d;
        	if(res==0)
        		break;
		}
    }
    return low-res;
}

void max_flow()
{
    int ans=0,res;
    while(bfs())
    {
    	//cout<<1<<endl;
    	for(int i=1;i<=n;++i)
    		cur[i]=head[i];
    	ans=ans+dfs(s,INF);
//    	while(res=dfs(s,INF))
//    		ans=ans+res;
    }
    cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
    int T;
    scanf("%d",&T);//>>T;
    while(T--)
    {
    	e=0;
        clean(head,-1);
        clean(edge,0);
        clean(dis,-1);
        scanf("%d%d",&n,&m);//>>n>>m;
        int s1=INF,t1=-INF;
        int x1,y1;
        for(int i=1;i<=n;++i)
        {
            scanf("%d%d",&x1,&y1);//>>x1>>y1;
            if(x1<s1)
                s1=x1,s=i;
            if(x1>t1)
                t1=x1,t=i;
        }
        int a,b,l;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&a,&b,&l);//>>a>>b>>l;
            add(a,b,l);
        }
        max_flow();
    }
    return 0;
}

还有一个奇怪的代码。。在学弧优化的时候写的，9978ms？？！！震惊！！竟然能过！！？？

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 998244353
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
struct node{
    int v,w,nxt;
    node(int _v=0,int _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[100005<<1];
int head[100005];
int dis[100005],cur[100005];
bool vis[100005];
int n,m;
int e,s,t;

void add(int u,int v,int w)
{
    edge[e]=node(v,w,head[u]);
    head[u]=e++;
    
    edge[e]=node(u,w,head[v]);
    head[v]=e++;
}

bool bfs()
{
    clean(vis,0);
    dis[s]=1;
    vis[s]=1;
    queue<int> que;
    que.push(s);
    while(que.size())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i+1;i=edge[i].nxt)
        {
        	int temp=edge[i].v;
        	if(vis[temp]||edge[i].w<=0)
        		continue;
        	dis[temp]=dis[u]+1;
        	vis[temp]=1;
        	que.push(temp);
//            if(dis[temp]==-1&&edge[i].w>0)
//            {
//                dis[temp]=dis[u]+1;
//                que.push(temp);
//            }
        }
    }
    return vis[t];
    //return dis[t]>-1;
}

int dfs(int u,int low)
{
    if(u==t||low==0)
        return low;
    int res=0;
    for(int &i=cur[u];i+1;i=edge[i].nxt)//遍历邻接表 
    {
    	int temp=edge[i].v,d;
        if(dis[temp]==dis[u]+1&&(d=dfs(temp,min(low,edge[i].w)))>0)
        {
        	edge[i].w-=d;
        	edge[i^1].w+=d;
        	res+=d;
        	low-=d;
        	if(low==0)
        		break;
		}
//		if(dis[temp]==dis[u]+1&&edge[i].w)
//        {
//        	int d=dfs(temp,min(low-res,edge[i].w));
//        	edge[i].w-=d;
//        	edge[i^1].w+=d;
//        	res+=d;
//        	if(res==low)
//        		break;
//		}
    }
    return res;
    
//    if(res==0)//最小值等于0，说明这条路不通 
//    	dis[u]=-2;
//    return res;
}

void max_flow()
{
    int ans=0,res;
    while(bfs())
    {
    	for(int i=1;i<=n;++i)
    		cur[i]=head[i];
    	ans=ans+dfs(s,INF);
//    	while(res=dfs(s,INF))
//    		ans=ans+res;
    }
    cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
    int T;
    scanf("%d",&T);//>>T;
    while(T--)
    {
    	e=0;
        clean(head,-1);
        clean(edge,0);
        scanf("%d%d",&n,&m);//>>n>>m;
        int s1=INF,t1=-INF;
        int x1,y1;
        for(int i=1;i<=n;++i)
        {
            scanf("%d%d",&x1,&y1);//>>x1>>y1;
            if(x1<s1)
                s1=x1,s=i;
            if(x1>t1)
                t1=x1,t=i;
        }
        int a,b,l;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&a,&b,&l);//>>a>>b>>l;
            add(a,b,l);
        }
        max_flow();
    }
    return 0;
}