hdu 3729 I'm Telling the Truth （二分图匹配）

I'm Telling the TruthTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1109 Accepted Submission(s): 557

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>//#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 200005#define MAXN 6000005#define mod 1000000007#define INF 0x3f3f3f3fusing namespace std;int n,m,cnt,ans;int anss[105];int from[maxn];bool use[maxn];vector<int>g[maxn];bool match(int x){ int i; for(i=0;i<g[x].size();i++) { if(!use[g[x][i]]) { use[g[x][i]]=1; if(from[g[x][i]]==-1||match(from[g[x][i]])) { from[g[x][i]]=x; return true ; } } } return false ;}void hungry(){ int i; memset(from,-1,sizeof(from)); for(i=n;i>=1;i--) { memset(use,0,sizeof(use)); if(match(i)) { ans++; anss[ans]=i; } }}int main(){ int i,j,t,u,v; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { g[i].clear(); } for(i=1;i<=n;i++) { scanf("%d%d",&u,&v); for(j=u;j<=v;j++) { g[i].push_back(j); } } ans=0; hungry(); printf("%d\n",ans); for(i=ans;i>1;i--) { printf("%d ",anss[i]); } printf("%d\n",anss[i]); } return 0;}