标签存档：图论

http://www.byvoid.com/blog/lpf24-solution/

这是线性规划与网络流的下载地址…

说明：

我都是不输出方案的

code：

#include using namespace std;
int m,n,g[101][101],v[101],link[101];

void Init(){
    cin >> m >> n;
    int x,y;
    while ((cin >> x >> y) && (x+y!=-2))
      g[x][y]=1;
}

bool Find(int k){
    for (int i=1;i<=n;i++)
      if (v[i]==0 && g[k][i]==1){
          v[i]=1;
          int q=link[i];
          link[i]=k;
          if (q==0 || Find(q)) return true;
          link[i]=q;
      }
    return false;
}

void Match(){
    memset(link,0,sizeof(link));
    int ans=0;
    for (int i=1;i<=m;i++){
        memset(v,0,sizeof(v));
        if (Find(i)) ans++;
    }
    if (ans==0) cout << "No Solution!" << endl;
           else cout << ans << endl;
}

int main(){
    freopen("air10.in","r",stdin);
    freopen("air10.ans","w",stdout);
    Init();
    Match();
    return 0;
}