[SGU 210]最大匹配、贪心**

【题目大意】 N个男的、N个女的（N<=400），互相匹配。每个男的有权值，求最后权值最大。 【算法分析】将男的按权值排序，然后根据这个顺序来最大匹配。匈牙利算法每次寻找交错轨的话，前面已匹配的节点绝不会再丢失匹配，所以根据这个性质，可以这么做。 【其它】SGU跑了近10分钟给了我一个CE。。。#include 994478 02.02.10 16:06 edward 210 .CPP Accepted 559 ms 2499 kb
【CODE】
#include #include #include #include using namespace std;
struct edge{int y; edge *next;};
struct data{int w,mark;}d[411];
int n,link[411],cover[411],ans[411];
edge *ls[411];
bool cmp(data x,data y){return x.w>y.w;}

void add(int x,int y){
edge *p=new edge;
p->y=y; p->next=ls[x]; ls[x]=p;
}

bool dfs(int k){
for (edge *t=ls[k];t;t=t->next)
if (!cover[t->y]){
cover[t->y]=1;
int q=link[t->y];
link[t->y]=k;
if (q==0 || dfs(q)) return true;
link[t->y]=q;
}   
return false;
}   

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
ls[i]=NULL;
scanf("%d",&d[i].w);
d[i].mark=i;
}
for (int i=1;i<=n;i++){
int num,x;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&x);
add(i,x);
}   
}   
sort(&d[1],&d[n+1],cmp);
for (int now=1;now<=n;now++){
memset(cover,0,sizeof(cover));
dfs(d[now].mark);
}
for (int i=1;i<=n;i++)
if (link[i]) ans[link[i]]=i;
for (int i=1;iprintf("%dn",ans[n]);
}