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得好惨】贴代码,感觉很清晰的样子~#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std; const int N=1000; vector<int> e[N]; int mat[N],n,m,on[N],cntn,cntm; bool cross(int x) { for(int i=0;i<e[x].size();i++) { int t=e[x][i]; if(!on[t]) { on[t]=1; if(!mat[t]||cross(mat[t])) { mat[t]=x; return 1; } } } return 0; } int c[N][N],r[N][N]; char s[N][N]; void init() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",s[i]); cntn=cntm=1; for(int i=0;i<n;i++) { int j; for(j=0;j<m;j++) if(s[i][j]=='*') { while(s[i][j]=='*') r[i][j++]=cntn; j--; cntn++; } } for(int j=0;j<m;j++) { int i; for(i=0;i<n;i++) if(s[i][j]=='*') { while(s[i][j]=='*')c[i++][j]=cntm; i--; cntm++; } } for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(s[i][j]=='*') e[c[i][j]].push_back(r[i][j]); int ans=0; for(int i=1;i<cntm;i++) { memset(on,0,sizeof(on)); if(cross(i)) ans++; } cout<<ans<<endl; } int main() { // freopen("in.txt","r",stdin); init(); // cout << "Hello world!" << endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator