Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题有没有用vector建图过的呀。。有的话发给我一份好吗?

Posted by 2011550321 at 2013-09-12 21:46:55 on Problem 2135
In Reply To:这题有没有用vector建图过的呀。。有的话发给我一份好吗? Posted by:athenaa at 2011-02-28 17:27:44
这个是我用vector来写的ac的代码:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int MAXN=1e9;

struct node
{
    int cost;
    int from;
    int to;
    int cap;
    int flow;
}edge[1010*1010];

vector<int>w[1010];
int mark[1010];
int get[1010];
int path[1010];
int pre[1010];
int step;

bool MCMF(int vstart,int vend,int &flow,int &cost)
{
    for(int ii=vstart;ii<=vend;ii++){mark[ii]=0;path[ii]=MAXN;get[ii]=MAXN;}
    queue<int>q;
    q.push(vstart);
    path[vstart]=0;
    pre[vstart]=vstart;
    while(!q.empty())
    {
        int tt=q.front();
        q.pop();
        mark[tt]=0;
        int len=w[tt].size();
        for(int ii=0;ii<len;ii++)
        {
            int son=w[tt][ii];
            node e=edge[son];
            if(e.cap>e.flow&&path[e.to]>path[tt]+e.cost)
            {
                path[e.to]=path[tt]+e.cost;
                get[e.to]=min(get[tt],e.cap-e.flow);
                pre[e.to]=son;
                if(!mark[e.to])
                {
                    q.push(e.to);
                    mark[e.to]=1;
                }
            }
        }
    }
    if(path[vend]==MAXN)return false;
    flow+=get[vend];
    cost+=path[vend]*get[vend];
    int uu=vend;
  //  cout<<path[vend]<<endl;
    while(uu!=vstart)
    {
        edge[pre[uu]].flow+=get[vend];
        edge[pre[uu]^1].flow-=get[vend];
        //cout<<edge[pre[uu]].from<<' '<<edge[pre[uu]].to<<' '<<edge[pre[uu]].cost<<endl;
        uu=edge[pre[uu]].from;
    }
    return true;
}
void add2(int ss,int ee,int cost,int many)
{
    w[ee].push_back(step);
    edge[step].from=ee;
    edge[step].to=ss;
    edge[step].cost=cost;
    edge[step].flow=0;
    edge[step++].cap=many;

    w[ss].push_back(step);
    edge[step].from=ss;
    edge[step].to=ee;
    edge[step].cost=-cost;
    edge[step].flow=0;
    edge[step++].cap=0;
}

void add1(int ss,int ee,int cost,int many,int kk)
{
    w[ss].push_back(step);
    edge[step].from=ss;
    edge[step].to=ee;
    edge[step].cost=cost;
    edge[step].flow=0;
    edge[step++].cap=many;

    w[ee].push_back(step);
    edge[step].from=ee;
    edge[step].to=ss;
    edge[step].cost=-cost;
    edge[step].flow=0;
    edge[step++].cap=0;
    if(kk==0)add2(ss,ee,cost,many);
    return ;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(edge,0,sizeof(edge));
        step=0;
        for(int ii=0;ii<=n+1;ii++)w[ii].clear();
        while(m--)
        {
            int x,y,t;
            scanf("%d%d%d",&x,&y,&t);
            add1(x,y,t,1,0);
        }
        add1(0,1,0,2,1);
        add1(n,n+1,0,2,1);
        int flow=0;
        int cost=0;
        while(MCMF(0,n+1,flow,cost));
        printf("%d\n",cost);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator