天天看點
傳回

poj2391Floyd+二分+最大流

好吧算增加了一個模闆吧。。

過兩天要校賽了，沒過的題先放着，這兩天把做過的整理整理。

構圖思路:将點拆分成2組，一組代表牛，一組代表遮蔽點，然後建構源點和彙點；

用floyd求出點與點之間的最大距離，根據最大距離開始二分，使距離小于mid的點在最大流中開路，若得出最大流等于牛的個數，mid減少，否則增大。求出答案。

這題注意一下構圖，先前的sap模闆會改變原圖的值，且構圖的時候注意雙向邊。

自己的代碼WA了。。。

///

經過好幾天的debug 在usaco上找到資料，結果證明我先前的那份模闆不能處理大資料。

 然後自己用這份模闆重新做了一遍，處理floyd上有錯 - -  wa好幾次。

模闆：

/*Floyd+最大流判定(拆點)+二分答案*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 405
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
	int u,v,w,next;
}E[200000];
int head[MAXN],ecnt;
int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN];
__int64 map[205][205];
int N,M,scr,sink,vn,num;
int A[205],B[205];
void Insert(int u,int v,int w)
{
	E[ecnt].u=u;
	E[ecnt].v=v;
	E[ecnt].w=w;
	E[ecnt].next=head[u];
	head[u]=ecnt++;
	E[ecnt].u=v;
	E[ecnt].v=u;
	E[ecnt].w=0;
	E[ecnt].next=head[v];
	head[v]=ecnt++;
}
void Init()
{
	int i,u,v;
	__int64 c;
	memset(map,-1,sizeof(map));
	scr=0;sink=2*N+1;vn=sink+1;num=0;
	for(i=1;i<=N;i++)
	{
		scanf("%d%d",&A[i],&B[i]);
		num+=A[i];
	}
	for(i=1;i<=M;i++)
	{
		scanf("%d%d%I64d",&u,&v,&c);
		if(map[u][v]==-1||map[u][v]>c)
		{map[u][v]=map[v][u]=c;}
	}
}
void Floyd()
{
	int i,j,k;
	for(k=1;k<=N;k++)
	{
		for(i=1;i<=N;i++)
		{
			if(i==k||map[i][k]==-1) continue;
			for(j=1;j<=N;j++)
			{
				if(j==k||i==j||map[j][k]==-1) continue;
				if(map[i][j]==-1||map[i][j]>map[i][k]+map[k][j])
					map[i][j]=map[i][k]+map[k][j];
			}
		}
	}
}
int Sap(int s,int t,int n)//核心代碼(模版)
{
    int ans=0,aug=INF;//aug表示增廣路的流量
    int i,v,u=pre[s]=s;
    for(i=0;i<=n;i++)
    {
        cur[i]=head[i];
        dis[i]=gap[i]=0;
    }
    gap[s]=n;
    bool flag;
    while(dis[s]<n)
    {
        flag=false;
        for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定義成int &j,why
        {
            v=E[j].v;
            if(E[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=true;//找到容許邊
                aug=min(aug,E[j].w);
                pre[v]=u;
                u=v;
                if(u==t)
                {
                    ans+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        E[cur[u]].w-=aug;
                        E[cur[u]^1].w+=aug;//注意
                    }
                    aug=INF;
                }
                break;//找到一條就退出
            }
        }
        if(flag) continue;
        int mindis=n;
        for(i=head[u];i!=-1;i=E[i].next)
        {
            v=E[i].v;
            if(E[i].w>0&&dis[v]<mindis)
            {
                mindis=dis[v];
                cur[u]=i;
            }
        }
        if((--gap[dis[u]])==0) break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return ans;
}
bool Judge(__int64 mid)//構圖+判定
{
	int i,j;
	memset(head,-1,sizeof(head));ecnt=0;
	for(i=1;i<=N;i++)
	{
		Insert(scr,i,A[i]);
		Insert(i+N,sink,B[i]);
		Insert(i,i+N,INF);
	}
	for(i=1;i<=N;i++)
	{
		for(j=i+1;j<=N;j++)
		{
			if(map[i][j]==-1) continue;
			if(map[i][j]<=mid)//注意要連入點-->出點(INF)
			{
				Insert(i,j+N,INF);
				Insert(j,i+N,INF);
			}
		}
	}
	return Sap(scr,sink,vn)==num;
}
void Solve()
{
	int i,j;
	__int64 l,r,mid,Max=0;
	Floyd();
	/*
	for(i=1;i<=N;i++)
	{
	for(j=1;j<=N;j++)
	printf("%I64d ",map[i][j]);
	printf("\n");
	}
	*/
	for(i=1;i<=N;i++)
	{
		for(j=i+1;j<=N;j++)
			Max=max(Max,map[i][j]);
	}
	l=0;r=Max;
	while(l!=r)
	{
		mid=(l+r)/2;
		if(Judge(mid))
			r=mid;
		else
			l=mid+1;
	}
	if(Judge(l))
		printf("%I64d\n",l);
	else
		printf("-1\n");
}
int main()
{
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		Init();
		Solve();
	}
	return 0;
}

自己根據這份模闆寫的代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 405
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
    int u,v,w,next;
}E[200000];
__int64 l;__int64 r;__int64 tmp;__int64 mid;
int head[MAXN],ecnt;
int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN];
__int64 map[205][205];
int N,M,scr,sink,vn,num;
int A[205],B[205],sum;
int k,c1,m,nn;
void Floyd()
{
    for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
    if(i!=k&&map[i][k]!=-1)
    for(int j=1;j<=N;j++)
    {
        if(i!=j&&j!=k&&map[k][j]!=-1)
        {
            if(map[i][j]==-1)
                map[i][j]=map[i][k]+map[k][j];
            else map[i][j]=map[i][j]>map[i][k]+map[k][j]?map[i][k]+map[k][j]:map[i][j];
        }
    }
}
void Insert(int u,int v,int w)
{
    E[ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt++;
    E[ecnt].u=v;
    E[ecnt].v=u;
    E[ecnt].w=0;
    E[ecnt].next=head[v];
    head[v]=ecnt++;
}
int Sap(int s,int t,int n)//核心代碼(模版)
{

    int ans=0,aug=INF;//aug表示增廣路的流量
    int i,v,u=pre[s]=s;
    for(i=0;i<=n;i++)
    {
        cur[i]=head[i];
        dis[i]=gap[i]=0;
    }
    gap[s]=n;
    bool flag;
    while(dis[s]<n)
    {
        flag=false;
        for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定義成int &j,why
        {
            v=E[j].v;
            if(E[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=true;//找到容許邊
                aug=min(aug,E[j].w);
                pre[v]=u;
                u=v;
                if(u==t)
                {
                    ans+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        E[cur[u]].w-=aug;
                        E[cur[u]^1].w+=aug;//注意
                    }
                    aug=INF;
                }
                break;//找到一條就退出
            }
        }
        if(flag) continue;
        int mindis=n;
        for(i=head[u];i!=-1;i=E[i].next)
        {
            v=E[i].v;
            if(E[i].w>0&&dis[v]<mindis)
            {
                mindis=dis[v];
                cur[u]=i;
            }
        }
        if((--gap[dis[u]])==0) break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return ans;
}
void build(__int64 mid)
{
        memset(head,-1,sizeof(head));ecnt=0;
        for(int i=1;i<=N;i++)//源點
        {
            Insert(scr,i,A[i]);
            Insert(i+N,sink,B[i]);
            Insert(i,i+N,INF);
        }
           for(int i=1;i<=N;i++)
           for(int j=i+1;j<=N;j++)
           if(map[i][j]!=-1&&map[i][j]<=mid)
           {
               Insert(i,j+N,INF);
               Insert(j,i+N,INF);
           }
}
bool judge(__int64 mid)
{
    build(mid);
    //cout<<l<<' '<<r<<endl;
    int ans=Sap(scr,sink,vn);
    //cout<<ans<<"!!!!!!!!!!"<<endl;
    return ans==sum;
}
int main()
{
   while(scanf("%d%d",&N,&M)!=EOF)
   {
       sum=0;scr=0;sink=2*N+1;vn=sink+1;
       memset(map,-1,sizeof(map));
       for(int i=1;i<=N;i++)
       {
           scanf("%d%d",&A[i],&B[i]);
           sum+=A[i];
       }
       for(int i=1;i<=M;i++)
       {
           int v,u;
           __int64 w;
           scanf("%d%d%I64d",&v,&u,&w);
            if(map[v][u]==-1||map[v][u]>w)
            {
                map[u][v]=w;
                map[v][u]=w;
            }
       }


       tmp=0;l=0;r=0;mid=0;
       Floyd();

       for(int i=1;i<=N;i++)   //找最短路的最大值
       for(int j=i+1;j<=N;j++)
       {
           if(map[i][j]!=-1&&map[i][j]>tmp)
           tmp=map[i][j];
       }

       r=tmp;
       //cout<<endl<<tmp<<endl;
       while(l!=r)
       {
           mid=(l+r)>>1;
           if(judge(mid))
           {
               r=mid;
           }
           else l=mid+1;
       }
       if(judge(l))
       printf("%I64d\n",l);
       else
        printf("-1\n");
   }
   return 0;
}

那份不能處理大資料的挫代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; __int64 l,r,mid; const int  maxn = 220; const int  inf =1000000000;//不要開太大 int  c[maxn][maxn]; int  q[maxn], pre[maxn]; int  level[maxn], gap[maxn]; __int64 map[maxn][maxn]; int A[maxn]; int B[maxn]; int INF =1000000000; int n, m; int s, t; int nn; int cnt,ans; void init_sap(){     memset(level,  1, sizeof (level));     memset(gap, 0, sizeof gap);     memset(pre, -1, sizeof pre);     int qs = 0, qe = 0;     q[qe++] = t;     level[t] = 0;     gap[ level[t] ] ++;     while(qs < qe){         int hd = q[qs++];         for(int i = 1; i <= n; i ++){             if(level[i] > n && c[i][hd] > 0){//level[i] >= n  也可以,why ?                 q[qe++] = i;                 level[i] = level[hd] + 1;                 gap[ level[i] ] ++;             }         }     } } int find_path(int u){     for(int i = 1; i <= n; i ++)       if(c[u][i] > 0 && level[u] == level[i] + 1) return i;     return -1; } int relabel(int u){     int  tmp = inf;     for(int i = 1; i <= n; i ++)       if(c[u][i] > 0 && tmp > level[i] + 1)         tmp = level[i] + 1;     if(tmp == inf) tmp = n;     return tmp; } int sap(){

    init_sap();     int  flow = 0, u = s;     while(level[s] <= n){         int  v = find_path(u);         if(v > 0){             pre[v] = u;             u = v;             if(u == t){                 int min_flow = inf;                 for(int i = t; i != s; i = pre[i])                   if(min_flow > c[ pre[i]][i])                     min_flow = c[ pre[i]][i];                 for(int i = t; i != s; i = pre[i]){                     c[pre[i]][i] -= min_flow;                     c[i][pre[i]] += min_flow;                 }                 flow += min_flow;                 u = s;             }         }else{             if(-- gap[ level[u]] == 0) return flow;             int  v = relabel(u);             gap[v] ++;             level[u] = v;             if(u != s) u = pre[u];         }     }     return flow; } void build() {         memset(c, 0, sizeof c);             for(int i=1;i<=nn;i++)             {                 c[s][i]=A[i];                 c[i+nn][t]=B[i];                 c[i][i+nn]=inf;             }             for(int i=1;i<=nn;i++)     //将map中小于mid的路打通c=inf             for(int j=1;j<=nn;j++)             {                 if(map[i][j]==-1)continue;                 if(map[i][j]<=mid)                 {                     c[i][j+nn]=inf;                     c[j][i+nn]=inf;                 }             }         } int main(){     while(~scanf("%d%d", &n, &m)){          //n為點 m為邊         nn=n;n=2*nn+2;         memset(map,-1,sizeof(map));         for(int i=1;i<=nn;i++)              //n的圖         {             for(int j=1;j<=nn;j++)             {                 if(i==j)map[i][j]=0;             }         }         s = 2*nn+1, t = 2*nn+2;cnt=0;          //牛的數量         for(int i=1;i<=nn;i++)           //加入源點和彙點的容量         {             scanf("%d%d",&A[i],&B[i]);             cnt+=A[i];         }         for(int i = 1; i <= m; i ++){             int u, v ;             __int64 w;             scanf("%d%d%I64d", &u, &v, &w);//雙向邊             if(map[u][v]==-1||w<map[u][v])             map[u][v]=map[v][u]=w;         }

        for(int k=1;k<=nn;k++)                //Floyd         for(int i=1;i<=nn;i++)         {             if(i==k||map[i][k]==-1)continue;             for(int j=1;j<=nn;j++)             {                 if(j==k||j==i||map[k][j]==-1)continue;                 if(map[i][j]==-1||map[i][j]>map[i][k]+map[k][j])                      map[i][j]=map[i][k]+map[k][j];             }         }         l=0,r=0; ans=0;         for(int i=1;i<=nn;i++)         {         for(int j=i+1;j<=nn;j++)             r=max(r,map[i][j]);         }         while(r!=l)       //二分         {             mid=(l+r)>>1;             build();             ans = sap();             if(ans==cnt)             {                r=mid;

            }             else  l=mid+1;         }         mid=l;         build();         ans=sap();         //r=inf;        // printf("%I64d\n",r);         //printf("%I64d %I64d %d %d\n",l,r,ans,cnt);         if(ans==cnt)         printf("%I64d\n",l);         else         printf("-1\n");     }     return 0; }

轉載于:https://www.cnblogs.com/amourjun/archive/2013/05/02/5134161.html

大資料
上一篇: Angular自定義管道（非原創）
下一篇: echarts自定義餅圖

繼續閱讀