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 |
看到网上题解都是千篇一律,说说我的建图,赋AC代码R和C看反了,贡献两次WA,哭死 #include <stdio.h> #include <string.h> #define N 110 #define MAXM 3000 struct point { int v, w, next; }a[MAXM]; int x[MAXM], y[MAXM]; int head[MAXM], match[MAXM], used[MAXM]; int cnt = 0, n, m; char ch[N][N]; void add(int u, int v, int w) { a[cnt].v = v; a[cnt].w = w; a[cnt].next = head[u]; head[u] = cnt++; } int dfs(int u) { int i; for(i = head[u]; i != -1; i = a[i].next) { int v = a[i].v; if(used[v] == 0) { used[v] = 1; int w = match[v]; if(w < 0 || dfs(w)) { match[v] = u; return 1; } } } return 0; } /*我们将每一行看成一个顶点分到集合a,将每一列看成一个顶点分到集合b。(不管是不是泥地) 接下来,假设我们将a中的每个顶点拆成c份(就是列的个数,这c个都表示该行),将b中每个顶点拆成r份(就是行的个数)。(其实不用那么多)*/ int main() { int i, j, ans = 0; scanf("%d%d", &n, &m); for(i = 0; i < n; i++) scanf("%s", ch[i]); memset(x, 0, sizeof(x)); memset(head, -1, sizeof(head)); memset(y, 0, sizeof(y)); //遍历草图,对每个为‘*’的点 for(i = 0; i < n; i++) for(j = 0; j < m; j++) { if(ch[i][j] == '*') { if(j == 0 || ch[i][j-1] == '.')//第一看它的左边是否是连通的泥地,不是就移动到下一个表示该行的点 x[i]++;//x[i]表示第i行第x[i]个点 if(i == 0 || ch[i-1][j] == '.')//第二看它的上边是否是连通的泥地,不是就移动到下一个表示该列的点 y[j]++;//同理y add(i*m+x[i], j*n+y[j], 1);//在第i行和第j列建立一条边 } } memset(match, -1, sizeof(match));//接下来就是普通的二分图了 for(i = 1; i <= n*m; i++) { memset(used, 0, sizeof(used)); if(dfs(i)) ans++; } 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