| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
WA的同学看看自己重新构图后的下标是否是从0开始的!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator