HDu 1498ハンガリーアルゴリズム

http://acm.hdu.edu.cn/showproblem.php?pid=1498
このテーマは昨夜長い間やっていたが、テーマの意味が分からなかったので、ネット上のコードを見て、徹底的に理解した.実は学生一人一人が風船の1つを選んで踏むことができて、後ろにはたくさんの学生が並んでいます.何色の風船が何人の学生が踏んで、それぞれの色の風船がK回踏まれた後、どの色の風船が存在するかを聞いた.
最初にやったばかりなのに、繰り返してたくさん出力していることに気づきました.後で他の人がset容器を使ったのを見て、自分もついて使って、46 msを提出して、とても優れていると思って、神牛のコードを探して、1つの15 msのを発見して、汗.
実は人のアルゴリズムは私と同じで、ただ人は2つの配列で記録します   に等しい  私のset容器.後でsetコンテナのようなシステムテンプレートを少なくしなければなりません.これは多かれ少なかれ私のプログラミング能力とコードの感度に影響を与えるからです.の
次は私のコード46 msです.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define maxn 105
#define mem(str,x) memset(str,(x),sizeof(str))
int map[maxn][maxn];
bool vis[maxn];
int flag[maxn][maxn];
int per[maxn];
int ans[maxn];
int n,k;
bool find(int x)
{
    for(int i=1;i<=n;i++){
        if( !vis[i] && flag[x][i] ){
                vis[i] = true;
            if(per[i] == -1 || find( per[i] ) ){
                per[i] = x;
                return true;
            }
        }
    }
    return false;
}
int hungry()
{
    int sum=0;
    for(int i=1;i<=n;i++) per[i] = -1;
    for(int i=1;i<=n;i++){
            mem(vis,false);
         sum+=find(i);
    }
    return sum;
}
int main()
{
     set< int > v;
    while(scanf("%d%d",&n,&k)&&n!=0&&k!=0){
            mem(map,0);  v.clear(); mem(ans,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                    int x;
                scanf("%d",&x);
                map[i][j] = x;
                v.insert( map[i][j] );
            }
        }
        if( k >= n ) printf("-1
");
        else{
                int anss=0;
             set<int>::iterator it;///       
           for(it = v.begin(); it != v.end(); it++ ){
               int color = *it;
               mem(flag,0);
               for(int i=1;i<=n;i++)
               for(int j=1;j<=n;j++){
                   if(map[i][j] == color)
                       flag[i][j] = 1;
                   else
                       flag[i][j] = 0;
               }
               int sum = hungry();
               if(sum > k) ans[anss++] = color;
           }
           if(anss==0) printf("-1
");
           else{
            for(int i = 0;i <anss;i++ ){
                printf("%d%c",ans[i],(i==anss-1)?'
':' ');
            }
           }
        }
    }
    return 0;
}

次は神牛コード15 msです.

#include"stdio.h" 
#include"string.h" 
#include"stdlib.h" 
int map[101][101],mark[101]; 
int v[101],link[101]; 
int a[101],color[101]; 
int k,n; 
int cmp(const void*a,const void*b) 
{ 
    return *(int*)a-*(int*)b; 
} 
int dfs(int i,int k) 
{ 
    int j; 
    for(j=1;j<=n;j++) 
    { 
        if(map[i][j]==k&&!v[j]) 
        { 
            v[j]=1; 
            if(link[j]==0||dfs(link[j],k)) 
            { 
                link[j]=i; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
int main() 
{ 
    int i,j,t,tt,ans; 
    while(scanf("%d%d",&n,&k)!=-1) 
    { 
        if(n==0&&k==0) 
            break; 
        memset(color,0,sizeof(color)); 
        memset(mark,0,sizeof(mark)); 
        t=0; 
        for(i=1;i<=n;i++) 
        { 
            for(j=1;j<=n;j++) 
            { 
                scanf("%d",&map[i][j]); 
                if(!mark[map[i][j]]) 
                { 
                    mark[map[i][j]]=1; 
                    color[t++]=map[i][j]; 
                } 
            } 
        } 
        tt=0; 
        for(i=0;i<t;i++) 
        { 
            ans=0; 
            memset(link,0,sizeof(link)); 
            for(j=1;j<=n;j++) 
            { 
                memset(v,0,sizeof(v)); 
                if(dfs(j,color[i])) 
                    ans++; 
            } 
            if(ans>k) 
                a[tt++]=color[i]; 
        } 
        if(tt==0) 
            printf("-1
"); 
        else 
        { 
            qsort(a,tt,sizeof(a[0]),cmp); 
            for(i=0;i<tt-1;i++) 
                printf("%d ",a[i]); 
            printf("%d
",a[i]); 
        } 
    } 
    return 0; 
}

実はまだ0 msの神牛がたくさん....