| ||||||||||
| 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