HDu 4280 Island Transport(最大ストリーム)

5708 ワード
図説
テーマ:
一部の島では、始点(最西)と終点(最東)を除いて、航路が交差しない航路(双方向)があり、各航路の客流量の上限が知られており、始点から終点まで最大の客流量を尋ねている.
裸で最大の流れを求める問題.
データ規模が大きい.
再帰的なDinicを使用して、人工的にスタックを拡張した後にc++が提出して、期限を押して過ぎました.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef __int64 LI;
typedef unsigned __int64 uLI;
typedef unsigned int uI;
typedef double db;
#define maxn 100005
#define inf 0x3f3f3f3f
struct Edge
{
    int to,cap,next;
}edge[maxn<<1];

int cnt,head[maxn],d[maxn],s,t;

inline void add(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].cap=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].cap=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

inline bool bfs()   //BFS     
{
    int u,i;
    queue q;
    q.push(s);
    memset(d,0,sizeof(d));
    d[s]=1;
    while(!q.empty())
    {
        u=q.front();q.pop();
        if(u==t) return true;   //            ，    DFS   ，                      。
        for(i=head[u];~i;i=edge[i].next){
            int v=edge[i].to;
            if(!d[v]&&edge[i].cap)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u,int a)  //    、            
{
    int flow=0,f,i;
    if(u==t||a==0) return a;
    for(i=head[u];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(edge[i].cap&&d[v]==d[u]+1)   //      0         
        {
            f=dfs(v,min(a,edge[i].cap));
            edge[i].cap-=f; //          
            edge[i^1].cap+=f;//     
            flow+=f;    //     
            a-=f;   //              f   
            if(!a) break;   //  0，             ，               f   0，             
        }
    }
    if(flow==0) d[u]=0; //           ，           
    return flow;
}

int dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}

int main()
{
    int a,b,c,T,x,y,i,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        int west=inf,east=-inf;
        for(i=1;i<=n;++i){
            scanf("%d%d",&x,&y);
            if(xeast) east=x,t=i;
        }
        for(i=0;i

次はISAPで、運行時間は上の半分です.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef unsigned int uI;
typedef double db;
#define maxn 100005
#define inf 0x3f3f3f3f
#define maxm 200005
#define maxq 100005
struct Edge{
    int to,cap,next;
}edge[maxm];

int Q[maxq],qhead,tail;//  
int cnt,head[maxn],d[maxn],cur[maxn],pre[maxn],num[maxn];
int sourse,sink,nv;//  、  、       
int n,m;

inline void add(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].cap=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].cap=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void bfs()
{
    memset(num,0,sizeof(num));
    memset(d,-1,sizeof(d));
    d[sink]=0;
    num[0]=1;
    qhead=tail=0;
    Q[tail++]=sink;
    while(qhead!=tail)
    {
        int u=Q[qhead++];
        for(int i=head[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(~d[v]) continue;
            d[v]=d[u]+1;
            Q[tail++]=v;
            num[d[v]]++;
        }
    }
}

int ISAP()
{
    int i;
    for(i=0;i<=n;++i) cur[i]=head[i];
    bfs();
    int flow=0,u=pre[sourse]=sourse;
    while(d[sink]edge[cur[i]].cap)
                {
                    f=edge[cur[i]].cap;
                    neck=i;
                }
            }
            for(i=sourse;i!=sink;i=edge[cur[i]].to)
            {
                edge[cur[i]].cap-=f;
                edge[cur[i]^1].cap+=f;
            }
            flow+=f;
            u=neck;
        }
        for(i=cur[u];~i;i=edge[i].next)
            if(d[edge[i].to]+1==d[u]&&edge[i].cap) break;
        if(~i)
        {
            cur[u]=i;
            pre[edge[i].to]=u;
            u=edge[i].to;
        }
        else{
            if(0==(--num[d[u]])) break;
            int mind=nv;
            for(i=head[u];~i;i=edge[i].next)
            {
                if(edge[i].cap&&mind>d[edge[i].to])
                {
                    cur[u]=i;
                    mind=d[edge[i].to];
                }
            }
            d[u]=mind+1;
            num[d[u]]++;
            u=pre[u];
        }
    }
    return flow;
}


int main()
{
    int a,b,c,T,x,y,i;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        int west=inf,east=-inf;
        for(i=1;i<=n;++i){
            scanf("%d%d",&x,&y);
            if(xeast) east=x,sink=i;
        }
        nv=sink+1;
        for(i=0;i
オレオレデザインパターン：Glocal Variable
[iOS/Swift] アプリ開発の実務的アプローチで学ぶデザインパターン ～Strategy/State～