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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

0_0 这题很奇怪么? sscanf 啊。1A。

Posted by dongshimou at 2014-07-25 15:03:14 on Problem 1459
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
#define acfun std::ios::sync_with_stdio(false)
using namespace std;

int n,np,nc,m;
struct lx
{
    int c,f;
};
lx g[301][301];
bool vis[301];
int path[301];
int flow[301];

void EK(int start,int thend)
{
    int maxflow=0;
    while(1)
    {
        for(int i=0;i<n+2;i++)
            vis[i]=0,path[i]=-1,flow[i]=0;
        queue<int>q;
        q.push(start);
        vis[start]=1,flow[start]=INF;
        while(!q.empty()&&!vis[thend])
        {
            int u=q.front();q.pop();
            for(int j=0;j<n+2;j++)
            {
                if(vis[j])continue;
                if(g[u][j].f<g[u][j].c)
                {
                    vis[j]=1;
                    path[j]=u;
                    flow[j]=min(flow[u],g[u][j].c-g[u][j].f);
                    q.push(j);

                }
                else if(g[j][u].f>0)
                {
                    vis[j]=1;
                    path[j]=u;
                    flow[j]=min(flow[u],g[j][u].f);
                    q.push(j);
                }
            }
        }
        if(!vis[thend]||flow[thend]==0)break;

        int v=thend,u=path[thend];
        int tmp=flow[thend];

        maxflow+=tmp;

        while(u!=-1)
        {
            if(g[u][v].f<g[u][v].c)
                g[u][v].f+=tmp;
            else
                g[v][u].f-=tmp;
            v=u,u=path[v];

        }
    }
    printf("%d\n",maxflow);
}

int main()
{
    while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
    {
        for(int i=0;i<n+2;i++)
            for(int j=0;j<n+2;j++)
            g[i][j].c=g[i][j].f=0;
        int u,v,c;
        char str[1001];
        while(m--)
        {
            scanf("%s",str);
            sscanf(str,"(%d,%d)%d",&u,&v,&c);
            g[u][v].c=c;

        }
        for(int i=0;i<np;i++)
        {
            scanf("%s",str);
            sscanf(str,"(%d)%d",&v,&c);
            g[n][v].c=c;
        }
        for(int i=0;i<nc;i++)
        {
            scanf("%s",str);
            sscanf(str,"(%d)%d",&u,&c);
            g[u][n+1].c=c;
        }
        EK(n,n+1);
    }
}

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