POJ 3041 Asteroids最小オーバーライド

問題の意味は分かりやすくて、問題を読み終わってもハンガリーのアルゴリズムを使うとは思わなかった.不思議だ.どうして最大のマッチングと一緒になったのだろうか.
最小オーバーライドの問題だったのか どのように見ているのは最小カバーの不思議な一つです http://ip96cns.blog.163.com/blog/static/170095192201102452319234/
このいくつかの言葉は比較的に好きです
 このような座標上の点を図の線に変換する方法は、座標系から図への変換思想であり、記憶に値する.
その中の隠れた関係は、座標系の1行、1列で、二分図上の2つの点セットに対応して、このように雲、ブロガーはすでに狂気に近い...」
 
あと何のkonning定理があって、最小カバー=最大マッチング数の不思議な2
コードは普通の最大のマッチングを求めて不思議ではありません 
貼り付け:

#include
#include
#include
#include
#include
#define nMAX 505
using namespace std;
int map[nMAX][nMAX],link[nMAX];
bool vs[nMAX];
int n;
bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(!vs[i]&&map[u][i])
        {
            vs[i]=1;
            if(!link[i]||dfs(link[i]))
            {
                link[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int i,cnt=0;
    memset(link,0,sizeof(link));
    for(i=1;i<=n;i++)
    {
        memset(vs,0,sizeof(vs));
        if(dfs(i))cnt++;
    }
    return cnt;
}
int main()
{
    int m,i,j;
    while(~scanf("%d%d",&n,&m))
    {
        memset(map,0,sizeof(map));
        while(m--)
        {
            scanf("%d%d",&i,&j);
            map[i][j]=1;
        }
      int ans=MaxMatch();
      printf("%d
",ans);
    }
    return 0;
}

　　
　　
 
 
 
自分が方法じゃない方法で
今でも正しいと思うのはWA 
コードを貼ってからバグを探します

//         ！！！  WA
#include
#include
#include
#include
#include
#include
using namespace std;
int cnt[1005],visit[502][502];
int cmp(const void * a,const void * b)
{
    return *(int*)b-*(int*)a;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int i,j,M,MM;
        M=m,MM=m;
        memset(cnt,0,sizeof(cnt));
        memset(visit,0,sizeof(visit));
        while(M--)
        {
            scanf("%d%d",&i,&j);
            visit[i-1][j-1]=1;
            cnt[i-1]++;
            cnt[j+n-1]++;
        }
        for(i=0;i1&&cnt[j+n]>1)MM++;
           }
        int ans=0;

        qsort(cnt,n*2,sizeof(cnt[0]),cmp);

        for(i=0;i

　　
転載先:https://www.cnblogs.com/sdau10kuaile/archive/2012/02/03/2336455.html