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 |
谢谢咯~In Reply To:一个灵异的现象。(附ac的代码) Posted by:fanhqme at 2008-10-03 13:57:10 > 我每次用fanhqme这个id提交题时,总比用AllwaysDead这个id得到的用时多16ms。(用一个代码)莫非每一个程序测评时得到的时间会加上这个id的人品值?麻烦大家试试我的code。 > #include <cstdio> > #include <string.h> > using namespace std; > char map[20][20],used[20]; > int Max_Match,fn[20],fm[20],N,M,res[20]; > int findpath(int u) > { > for (int v=0;v<M;v++)if (used[v]==0 && map[u][v]){ > used[v]=1; > if (fm[v]==-1 || findpath(fm[v])){ > return fn[u]=v,fm[v]=u,1; > } > } > return 0; > } > int Hungary() > { > Max_Match=0; > memset(fn,0xff,sizeof(fn)); > memset(fm,0xff,sizeof(fm)); > for (int i=0;i<N;i++)if (fn[i]==-1){ > memset(used,0,sizeof(used)); > Max_Match+=findpath(i); > } > return Max_Match; > } > void getPerfectMatch() > { > int j; > M=N; > for (int i=0;i<N;i++){ > for (j=0;j<N;j++)if (map[i][j]){ > map[i][j]=0; > if (Hungary()!=N){map[i][j]=1;break;} > map[i][j]=1; > } > res[i]=(j==N?-1:j); > } > } > int chkstr(char *a,char *b){while (*a || *b)if (*(a++)!=*(b++))return 0;return 1;} > void cpystr(char *a,char *b){while (*b)*(a++)=*(b++);*a=0;} > int chkord(char *a,char *b){while (*a || *b){if (*a > *b)return 1;if (*(a++) < *(b++))return -1;}return 0;} > int main() > { > char names[20][50],ids[20][50],living[20],z,chs[50]; > int criminal,i,t,R[20]; > scanf("%d",&N); > for (int i=0;i<N;i++)scanf("%s",ids[i]); > memset(map,0xff,sizeof(map)); > memset(living,0,sizeof(living)); > scanf("\n"); > criminal=0; > for (scanf("%c",&z);z!='Q';scanf("%c",&z)){scanf("%s",chs);scanf("\n"); > switch (z){ > case 'E': > for (i=0;i<criminal && chkstr(chs,names[i])==0;i++); > if (i==criminal)cpystr(names[criminal++],chs); > living[i]=1;break; > case 'L': > for (i=0;i<criminal && chkstr(chs,names[i])==0;i++); > living[i]=0;break; > case 'M': > for (i=0;i<N && chkstr(chs,ids[i])==0;i++); > for (int j=0;j<criminal;j++) > if (living[j]==0)map[j][i]=0; > for (int j=criminal;j<N;j++)map[j][i]=0; > break; > } > } > getPerfectMatch(); > for (int i=0;i<N;i++)R[i]=i; > for (int i=0;i<N;i++)for (int j=i;j<N;j++)if (chkord(names[R[i]],names[R[j]])==1){t=R[i];R[i]=R[j];R[j]=t;} > for (int i=0;i<N;i++){ > printf("%s:",names[R[i]]); > if (res[R[i]]==-1)printf("???\n"); > else printf("%s\n",ids[res[R[i]]]); > } > getchar();getchar();getchar();getchar(); > return 0; > } > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator