sicily 1684

//找匹配，要求保证最大权有最小值 //一开始开挂 优先队列+无限增广 直接水 3.04s过，发现status都1s内的。。那么水 //修改保留每次增边已得匹配边 直接0.1s过~~~ #include <iostream> #include <queue> #include <cstring> #include <cstdio> #define INF (1<<29) using namespace std; int n,v,u,d; int _in[501]; //_in标记已获增广的女点 int h[501],y[501],_link[501][501]; //h y 是存男资料 _link 女有_link[x][0]合法邻接 int linky[501]; //男y的匹配边 bool _usedx[501],_usedy[501]; struct Node { int x,y; int value; }w[501][501]; bool operator > ( Node a,Node b) { return a.value > b.value; } priority_queue< Node,vector<Node>,greater<Node> > q; //一次增广找不到就加一条边，优先队列保证 最大边有最小值 bool find( int x ) //一般一般的增广 { _usedx[x] = true; for( int i = 1;i <= _link[x][0];i++ ) { if( _usedy[_link[x][i]] ) continue; _usedy[_link[x][i]] = true; if( linky[_link[x][i]] == -1 || find( linky[_link[x][i]] ) ) { linky[_link[x][i]] = x; return true; } } return false; } int main() { //freopen("1.txt","r",stdin); while( scanf("%d",&n) && n != 0 ) { memset( _in,0,sizeof(_in) ); for( int i = 0;i < n;i++ ) linky[i] = -1; for( int i = 0;i < n;i++ ) _link[i][0] = 0; while ( !q.empty() ) q.pop(); for( int i = 0;i < n;i++ ) scanf("%d%d",h+i,y+i); for( int i = 0;i < n;i++ ) { scanf( "%d%d",&v,&u ); for( int j = 0;j < n;j++ ) { w[i][j].x = i; w[i][j].y = j; w[i][j].value = ( h[j] - v )*(h[j] - v) + (y[j]-u)*(y[j]-u); q.push( w[i][j] ); } } int i = 0; Node kk; while( true ) { if( i == n ) break; //匹配完备 kk = q.top(); q.pop(); _link[kk.x][++_link[kk.x][0]] = kk.y; for( i = 0;i < n;i++ ) { if( _in[i] ) continue; memset( _usedx,false,sizeof(_usedx) ); memset( _usedy,false,sizeof(_usedy) ); if( !find( i ) ) break; _in[i] = 1; } } cout<<kk.value<<endl; } return 0; }