Yavin(ijɳ²èµÄ´úÂë¿â)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int NUM=1500+100;
const int MAX=300000+10;
const int INF=2147480000;

priority_queue< pair<int,int> > q;

struct Edge
{
    int s,t,next;
    int c,flow;
}e[MAX*2];
int res[NUM],h[NUM];
int begin[NUM],top;

int n,m,L;
int level[NUM],S,T;
int gap[MAX];
int num[MAX];

void add(int x,int y,int c)
{
    num[top/2+1]=top;
    e[top].s=x;e[top].t=y;e[top].c=c;
    e[top].next=begin[x];begin[x]=top++;
    e[top].s=y;e[top].t=x;e[top].c=0;
    e[top].next=begin[y];begin[y]=top++;
}

int que[MAX],first,last,hash[MAX];

void SPFA()
{
    memset(h,-1,sizeof h);
    que[last++]=T;
    h[T]=0;hash[T]=1;
    int u,v,i;
    while(first<last)
    {
        u=que[first++];
        hash[u]=0;
        for(i=begin[u];i!=-1;i=e[i].next)
        {
            if(!e[i].c)
            {
                v=e[i].t;
                if(h[v]==-1||h[v]>h[u]+1)
                {
                    h[v]=h[u]+1;
                    if(!hash[v])que[last++]=v;
                    hash[v]=1;
                }
            }
        }
    }
    memset(hash,0,sizeof hash);
}

void push(int i)
{
    int u=e[i].s,v=e[i].t;
    int temp=min(e[i].c-e[i].flow,res[u]);
    if(temp>0)
    {
        res[u]-=temp;
        res[v]+=temp;
        if(!hash[v])
        {
            q.push(make_pair(h[v],v));
            hash[v]=1;
        }
        e[i].flow+=temp;
        e[i^1].flow-=temp;
    }
}

void pre(int first)
{
    memset(gap,0,sizeof gap);
    memset(res,0,sizeof res);
    int i;
    for(i=0;i<top;++i)
        e[i].flow=0;
    SPFA();
    res[S]=first;
    hash[S]=1;
    q.push(make_pair(h[S],S));
    for(i=1;i<=n;++i)
        ++gap[h[i]];
}

void push_relable(int u)
{
    hash[u]=0;
    int m,i;
    while(res[u]&&h[u]<2*n+1)
    {
        m=h[u]-1;
        for(i=begin[u];i!=-1;i=e[i].next)
            if(m==h[e[i].t]&&e[i].flow<e[i].c)
            {
                push(i);
                if(res[u]==0)
                    break;
            }
        if(!res[u])break;
        m=INF;
        for(i=begin[u];i!=-1;i=e[i].next)
        {
            if(e[i].flow<e[i].c)
            {
                m=min(h[e[i].t],m);
            }
        }
        if(m>=2*n+1)break;
        if(m+1!=h[u])
        {
            --gap[h[u]];
            if(!gap[h[u]])
            {
                for(i=1;i<=n;++i)
                    if(h[i]>h[u]&&h[i]<2*n+1)
                    {
                        --gap[h[i]];
                        ++gap[h[i]=2*n+1];
                    }
            }
            h[u]=m+1;
            gap[h[u]]++;
        }
    }
}

void maxflow()
{
    pre(INF);
    pair<int,int> now;
    while(!q.empty())
    {
        now=q.top();q.pop();
        if(now.second!=T)push_relable(now.second);
    }
    pre(res[T]);
    while(!q.empty())
    {
        now=q.top();q.pop();
        if(now.second!=T)push_relable(now.second);
    }
    int i;
    for(i=1;i<=m;++i)
        printf("%d\n",e[num[i]].flow);
}

void init()
{
    memset(begin,-1,sizeof begin);
    int i,x,y,c;
    scanf("%d %d %d",&n,&m,&L);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&level[i]);
        if(level[i]==1)S=i;
        if(level[i]==L)T=i;
    }
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        add(x,y,c);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    #endif
    init();
    maxflow();
}