首页 > 代码库 > poj3565Ants【最小权匹配】
poj3565Ants【最小权匹配】
大意：
左图为一个坐标轴上的点 其中黑点代表ants 白点代表apple 问怎样安排ants匹配apple才能使人一两条边不想交
分析：
如左图，我们假设a->d,b->c为一个最佳匹配 交点为e
那么ad+bc = ae+ ed + be + ec = (ae + ec) + (be + ed) 该值大于ac+bd
所以匹配为最佳匹配不成立
因此我们只要求出二分图的最小匹配就是结果了
但是wa了；
wa的代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const long long maxn = 105; 7 const long long INF = 10000000000; 8 9 10 long long W[maxn][maxn];11 long long Lx[maxn], Ly[maxn];12 long long Left[maxn];13 bool S[maxn], T[maxn];14 15 long long n;16 17 bool match(long long i) {18 S[i] = true;19 for(long long j = 1; j <= n; j++) if (Lx[i]+Ly[j] == W[i][j] && !T[j]){20 T[j] = true;21 if (!Left[j] || match(Left[j])){22 Left[j] = i;23 return true;24 }25 }26 return false;27 }28 29 void update() {30 long long a = INF;31 for(long long i = 1; i <= n; i++) if(S[i])32 for(long long j = 1; j <= n; j++) if(!T[j])33 a = min(a, Lx[i]+Ly[j] - W[i][j]);34 for(long long i = 1; i <= n; i++) {35 if(S[i]) Lx[i] -= a;36 if(T[i]) Ly[i] += a;37 }38 }39 40 void KM() {41 for(long long i = 1; i <= n; i++) {42 Left[i] = Lx[i] = Ly[i] = 0;43 for(long long j = 1; j <= n; j++)44 Lx[i] = max(Lx[i], W[i][j]);45 }46 for(long long i = 1; i <= n; i++) {47 for(;;) {48 for(long long j = 1; j <= n; j++) S[j] = T[j] = false;49 if(match(i)) break; else update();50 }51 }52 }53 54 55 struct Node {56 long long x, y;57 }ant[maxn], apple[maxn];58 59 60 long long dist(Node n1, Node n2) {61 return (n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y);62 }63 64 int main() {65 while(EOF != scanf("%lld",&n)) {66 for(long long i = 1; i <= n; i++) scanf("%lld %lld",&ant[i].x, &ant[i].y);67 for(long long i = 1; i <= n; i++) scanf("%lld %lld",&apple[i].x, &apple[i].y);68 memset(W, 0, sizeof(W));69 for(long long i = 1; i <= n; i++) {70 for(long long j = 1; j <= n; j++) {71 W[i][j] = -dist(apple[i], ant[j]);72 }73 }74 KM();75 for(long long i = 1; i <= n; i++) {76 printf("%lld\n",Left[i]);77 }78 }79 return 0;80 }
想了好长时间终于知道哪儿错了
我只是用的距离的平方做的比较
也就是说 a^2 + b ^ 2 > c ^ c + d ^ 2 不能推出 a + b > c + d
比如1^2 + 100^2 > 50 ^ 2 + 51 ^2 但是 1 + 100 < 51 + 52
所以平方比较是错的
ac代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const int maxn = 105; 8 const double INF = 1000000000; 9 10 double W[maxn][maxn];11 double Lx[maxn], Ly[maxn];12 int Left[maxn];13 bool S[maxn], T[maxn];14 15 int n;16 17 bool match(int i) {18 S[i] = true;19 for(int j = 1; j <= n; j++) if ( (abs(Lx[i]+Ly[j] - W[i][j]) < 0.00000001) && !T[j]){20 T[j] = true;21 if (!Left[j] || match(Left[j])){22 Left[j] = i;23 return true;24 }25 }26 return false;27 }28 29 void update() {30 double a = INF;31 for(int i = 1; i <= n; i++) if(S[i])32 for(int j = 1; j <= n; j++) if(!T[j])33 a = min(a, Lx[i]+Ly[j] - W[i][j]);34 for(int i = 1; i <= n; i++) {35 if(S[i]) Lx[i] -= a;36 if(T[i]) Ly[i] += a;37 }38 }39 40 void KM() {41 for(int i = 1; i <= n; i++) {42 Left[i] = 0;43 Lx[i] = Ly[i] = 0.0;44 for(int j = 1; j <= n; j++)45 Lx[i] = max(Lx[i], W[i][j]);46 }47 for(int i = 1; i <= n; i++) {48 for(;;) {49 for(int j = 1; j <= n; j++) S[j] = T[j] = false;50 if(match(i)) break; else update();51 }52 }53 }54 55 struct Node {56 double x, y;57 }ant[maxn], apple[maxn];58 59 double dist(Node n1, Node n2) {60 return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));61 }62 63 int main() {64 //freopen("3565.txt","r",stdin);65 while(EOF != scanf("%d",&n)) {66 for(int i = 1; i <= n; i++) scanf("%lf %lf",&ant[i].x, &ant[i].y);67 for(int i = 1; i <= n; i++) scanf("%lf %lf",&apple[i].x, &apple[i].y);68 memset(W, 0, sizeof(W));69 for(int i = 1; i <= n; i++) {70 for(int j = 1; j <= n; j++) {71 W[i][j] = -dist(apple[i], ant[j]);72 }73 }74 KM();75 for(int i = 1; i <= n; i++) {76 printf("%d\n",Left[i]);77 }78 }79 return 0;80 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。