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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

WA的同学看看自己重新构图后的下标是否是从0开始的!

Posted by 134115060058 at 2015-08-11 08:10:51 on Problem 3189
WA的同学看看自己重新构图后的下标是否是从0开始的!,若是从0开始就WA从1开始就AC
下面附上一组AC代码,不信的同学可以试试哦

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define INF 0x3fffffff
#define maxn 1255
int n, m;///n 只牛  m个牛棚
bool vis[maxn];
int limt[maxn];///代表牛棚所能容纳的最大数量
vector<vector<int> > G;
vector<vector<int> > P;///用来保存匹配的数据

bool Find(int u,int L,int R)
{
    for(int i=L; i<=R; i++)///遍历u的前k条边
    {
        int v = G[u][i-1];
        if( !vis[v] )
        {
            vis[v] = true;
            if(P[v].size() < limt[v])
            {
                P[v].push_back(u);
                return true;
            }
            for(int j=0; j<P[v].size(); j++)
            {
                if( Find(P[v][j], L, R) )
                {
                    P[v].erase(P[v].begin()+j);
                    P[v].push_back(u);
                    return true;
                }
            }
        }
    }
    return false;
}

bool solve(int L,int R)
{
    P.clear();
    P.resize(m+10);
    for(int i=1; i<=n; i++)
    {
        memset(vis, false, sizeof(vis));
        if( !Find(i, L, R) )
            return false;
    }
    return true;
}

int main()
{
    while(scanf("%d %d",&n, &m) != EOF)
    {
        G.clear();
        G.resize(n+10);

        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                int a;
                scanf("%d", &a);
                G[i].push_back(a);///保存每只牛心中的排名
            }
        }
        for(int i=1; i<=m; i++)
            scanf("%d", &limt[i]);
        int ans = INF;
        for(int i=1; i<=m; i++)///枚举一下。我们只允许选择前i个牛棚到j个牛棚
        {
            for(int j=i; j<=m; j++)
            {
                if(j-i+1 > ans)
                    break;
                if( solve(i, j) )
                    ans = j - i + 1;
            }
        }
        printf("%d\n", ans);
    }
    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