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