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

简单易懂的代码来了!!!!

Posted by 14151503308 at 2017-08-05 16:06:10 on Problem 1149
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 99999999
using namespace std;
int s,t,n,m;
int mp[105][105];
int ma[105][105];
int pig[1000],last[1000];
int q[1000000],pre[1000],a[1000];
int main()
{
    int i,j,num,k,sum=0;
    scanf("%d%d",&m,&n);
    s=0,t=n+1;
    memset(last,0,sizeof(last));
    memset(mp,0,sizeof(mp));
    for(i=1;i<=m;i++)
        scanf("%d",&pig[i]);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&num);
        for(j=1;j<=num;j++)
        {
            scanf("%d",&k);
            if(last[k]==0)
                mp[s][i]=mp[s][i]+pig[k];
            else
                mp[last[k]][i]=N;
            last[k]=i;
        }
        scanf("%d",&mp[i][t]);
    }
    while(1)
    {
        memset(a,0,sizeof(a));
        int left=0,right=0;
        right++;
        q[right]=0;
        a[0]=N;
        while(left!=right)
        {
            left++;
            int p=q[left];
            for(i=s;i<=t;i++)
            {
                if(mp[p][i]>0&&a[i]==0)
                {
                    pre[i]=p;
                    a[i]=min(a[p],mp[p][i]);
                    right++;
                    q[right]=i;
                }
            }
        }
        if(a[t]==0)
            break;
        for(i=t;i!=0;i=pre[i])
        {
            int M=pre[i];
            mp[M][i]-=a[t];
            mp[i][M]+=a[t];
        }
        sum+=a[t];
    }
    cout<<sum<<endl;
    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