POJ 1274 / POJ 1469 / POJ 2239 二分图最大匹配-白红宇

POJ 1274 / POJ 1469 / POJ 2239 二分图最大匹配

阅读量：5875 次

发布时间：2019-06-19

本文共 3238 字，大约阅读时间需要 10 分钟。

都是一些很裸的二分图最大匹配.

纯当复习了.

POJ 1274

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define bug(s) cout<<#s<<"="<
        <<" "inline int Rint() {int x; scanf("%d", &x); return x;}#define MAXN 500vector
         
           G[MAXN];int vis[MAXN];int flag[MAXN]; //0-未盖 / 对应点-已盖int n, m;int dfs(int u){ for(int i=0; i<(int)G[u].size(); i++) { int v = G[u][i]; if(!vis[v]) //未访问 { vis[v] = 1; if(!flag[v] || dfs(flag[v])) //!!不是dfs(v) -> dfs(flag[v]) 对应点 { flag[v] = u; return 1; } } } return 0;}int hungary(){ memset(flag, 0, sizeof(flag)); int ans=0; for(int i=1; i<=n; i++) //集合X中点 1~m { memset(vis, 0, sizeof(vis)); if(dfs(i)) ans++; } return ans;}void print_ans() //输出匹配M{ for(int i=n+1; i<=n+n; i++) //flag[v]=u...v=m+1~n if(flag[i]) //v为盖点，输出对应的匹配边 { printf("%d->%d\n", flag[i], i); }}int main(){ while(scanf("%d%d", &n, &m)==2) { for(int i=1; i<=n; i++) { if(!G[i].empty()) G[i].clear(); } for(int i=1; i<=n; i++) { //bug(i); int v; char ch; int cnt = Rint(); while(cnt--) { v = Rint(); //bug(v); G[i].push_back(v+n); //if(ch == '\n') break; } //cout<

POJ 1469

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            using namespace std;inline int Rint() { int x; scanf("%d", &x); return x; }inline int max(int x, int y) { return (x>y)? x: y; }inline int min(int x, int y) { return (x
            
             =(b);i--)#define REP(x) for(int i=0; i<(x); i++)typedef long long int64;#define INF (1<<30)#define bug(s) cout<<#s<<"="<
             <<" "#define MAXN 400#define MAXM MAXN*MAXN//int G[MAXN][MAXN]; //{U}->{V}int fa[MAXM], next[MAXM], u[MAXM], v[MAXM], w[MAXM], idx; //边集数组前向星, 表头后面只能跟边, 因为若跟点无法确定下一个点信息int flag[MAXN]; //盖, flag[{V}] = {U}int vis[MAXN]; //dfs访问标记, 只对Vint n, m;void addedge(int tu, int tv, int tw){ u[idx] = tu; v[idx] = tv; w[idx] = tw; next[idx] = fa[tu]; fa[tu] = idx++;}int dfs(int tu){ //vis[u] = 1; for(int e = fa[tu]; e!=-1; e = next[e]) { int tv = v[e]; if(vis[tv]) continue; vis[tv] = 1; if(!flag[tv] || dfs(flag[tv])) { //bug(v);bug(u)<

POJ 2239

这题只要把(星期, 班级)对, hash一下.就行

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            using namespace std;inline int Rint() { int x; scanf("%d", &x); return x; }inline int max(int x, int y) { return (x>y)? x: y; }inline int min(int x, int y) { return (x
            
             =(b);i--)#define REP(x) for(int i=0; i<(x); i++)typedef long long int64;#define INF (1<<30)#define bug(s) cout<<#s<<"="<
             <<" "#define MAXN 1000#define MAXM MAXN*MAXN//int G[MAXN][MAXN]; //{U}->{V}int fa[MAXM], next[MAXM], u[MAXM], v[MAXM], w[MAXM], idx; //边集数组前向星, 表头后面只能跟边, 因为若跟点无法确定下一个点信息int flag[MAXN]; //盖, flag[{V}] = {U}int vis[MAXN]; //dfs访问标记, 只对Vint n, m;void addedge(int tu, int tv, int tw){ u[idx] = tu; v[idx] = tv; w[idx] = tw; next[idx] = fa[tu]; fa[tu] = idx++;}int dfs(int tu){ //vis[u] = 1; for(int e = fa[tu]; e!=-1; e = next[e]) { int tv = v[e]; if(vis[tv]) continue; vis[tv] = 1; if(!flag[tv] || dfs(flag[tv])) { //bug(v);bug(u)<