Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

看高手的代码很有帮助啊, 在没人教的情况下

Posted by 00448247 at 2009-04-09 21:12:08 on Problem 1043
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator