hdu 3729（二分图匹配）

/*中午在机房等外卖的时候看了看网上的板子，闲着没事又写了一发*/ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=100000+10; int line[100][maxn]; const int inf=0x3f3f3f3f; int pp[maxn]; int cc[100]; bool used[maxn]; int t,n; int mini,maxi; bool findline(int x) { for(int i=mini;i<=maxi;i++) if(line[x][i]&&!used[i]) { used[i]=1; if(pp[i]==0||findline(pp[i])) { pp[i]=x; return true; } } return false; } int main() { scanf("%d",&t); while(t--) { memset(line,0,sizeof(line)); memset(pp,0,sizeof(pp)); scanf("%d",&n); mini=inf,maxi=0; for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); for(int j=a;j<=b;j++) line[i][j]=1; mini=min(mini,a); maxi=max(maxi,b); } int cnt=0; for(int i=n;i>=1;i--) { memset(used,0,sizeof(used)); if(findline(i)) cc[cnt++]=i; } printf("%d\n",cnt); sort(cc,cc+cnt); for(int i=0;i<cnt;i++) { if(i) printf(" "); printf("%d",cc[i]); } printf("\n"); } return 0; }

 

二分图匹配，应该叫匈牙利算法，以前做过这种题，看明白了思想，板子忘了，无奈只能看白书上的板子，这个板子有点乱，比如1，2，3匹配1，2，3就会乱匹配，建议还是去网上学学好的板子，这里我用x和N+X区分了匹配项(下面是白书的板子，上面是网上的板子，上面是后来加的）

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int maxn=100000+10; vector<int> G[2*maxn]; int match[maxn*2]; bool used[maxn*2]; int n,t; bool dfs(int v) { used[v]=true; for(int i=0;i<G[v].size();i++) { int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[u]=v; match[v]=u; return true; } } return false; } int main() { scanf("%d",&t); while(t--) { for(int i=1;i<=n;i++) G[i].clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); a=100000+a;//区分匹配项 b=100000+b; for(int j=a;j<=b;j++) { G[i].push_back(j); G[j].push_back(i); } } int res=0; int cc[70]; memset(match,-1,sizeof(match)); for(int i=n;i>=1;i--) { if(match[i]<0) { memset(used,0,sizeof(used)); if(dfs(i)) { cc[res]=i; res++; } } } sort(cc,cc+res); printf("%d\n",res); for(int i=0;i<res;i++) { if(i) printf(" "); printf("%d",cc[i]); } printf("\n"); } return 0; }

 

转载于:https://www.cnblogs.com/Wangwanxiang/p/7257566.html