首页 > 代码库 > uva11134 相互不攻击的车

uva11134 相互不攻击的车

2024-07-15 10:21:31   220人阅读

/*uva11134
在N*N(1<=N<=5000)的棋盘上放置N个车，使它们相互不攻击。
但是车有划定的区间放置。
求解一种方案，是的每个车能放置，没有一种满足，输出impossible
思路：
这种放置车的问题，一般思考到二分图最大匹配上。
因为要求出到底放置到哪个位置，所以要记录下来匹配的点。
我们发现行和列是可以分类讨论的（因为给定的区间是一个矩形，这样，即使选定了某一行放置，所有的列还是可供选择的）
整理一下流程：例如行：
对车编号1--N，对行编号1--N;
如果一个车i能放置到第j行，我们在i和j之间连一条i到j的有向边。
我们现在要找到一个最大匹配，一个匹配（即一条边）的逻辑含义是i车放在j行。
这样，我们思考匹配寻找的过程。若 1->2,1->3,1->4,2->3,2->4,2->5.
*/

 1 #include <iostream> 2 #include <cmath> 3 #include <algorithm> 4 #include <string.h> 5 #include <stdio.h> 6 #include <set> 7 #include <stack> 8 #include <vector> 9 #define maxn 501010 using namespace std;11 12 int N;13 struct Line{14     int l,r,k;15     bool operator<(const Line & X)const{16         if (l==X.l) return r<X.r;else return l<X.l;17     }18     void print(){19         printf("%d:[%d,%d]\n",k,l,r);20     }21 }X[maxn],Y[maxn];22 int posX[maxn],posY[maxn];23 int xl[maxn],yl[maxn],xr[maxn],yr[maxn];24 void read(){25     for(int i=1;i<=N;i++){26         scanf("%d%d%d%d",&xl[i],&yl[i],&xr[i],&yr[i]);27         X[i-1]=(Line){xl[i],xr[i],i};28         Y[i-1]=(Line){yl[i],yr[i],i};29     }30 }31 bool solveX(){32     sort(X,X+N);33     int p=0;34     for(int i=1;i<=N;i++){35         Line L=X[p];36         L.print();37         if(L.l<=i && L.r>=i) {38             p++;39             posX[L.k]=i;40             cout<<"choose"<<i<<endl;41         }else return false;42     }43     return true;44 }45 bool solveY(){46     sort(Y,Y+N);47     int p=0;48     for(int i=1;i<=N;i++){49         Line L=Y[p];50         if (L.l<=i && L.r>=i) {51             p++;52             posY[L.k]=i;53         }else return false;54     }55     return true;56 }57 void printans(){58     for(int i=1;i<=N;i++){59         printf("%d %d\n",posX[i],posY[i]);60     }61     return ;62 }63 int main(){64     while(~scanf("%d",&N) && N>0){65         read();66         if (solveX() && solveY()) printans();67         else printf("IMPOSSIBLE\n");68     }69     return 0;70 }

 


联系
我们