題意：

　　給出n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的坐標(biāo)，要求用n條不相交的線段把它們連接起來(lái)，其中每條線段恰好連接一個(gè)白點(diǎn)和一個(gè)黑點(diǎn)，每個(gè)點(diǎn)恰好連接到一條線段

解析：

　　帶入負(fù)的歐幾里得距離求就好了

　　假設(shè)a1-b1 與 a2-b2相交 則dis(a1, b1) + dis(a2, b2) 一定大于 dis(a1, b2) + dis(a2, b1)?

　　四邊形的對(duì)角線一定大于兩條對(duì)邊。。。

　　所以。。邊的權(quán)值取負(fù)的歐幾里得距離。。來(lái)一次km就好了 ? km是求最大 ?而負(fù)的最大 對(duì)應(yīng)整的最小 而整的最小 又能對(duì)應(yīng)不相交

#include <iostream> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> #include <vector> #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; const int maxn = 220, INF = 0x7fffffff; const double eps = 1e-8; int usedx[maxn], usedy[maxn], cx[maxn], cy[maxn]; int nx, ny, n, max_value; double minn; double w[maxn][maxn], bx[maxn], by[maxn], slack[maxn]; struct node {double x, y; }Node[maxn], Edge[maxn];int dcmp(double x) {if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; }bool dfs(int u) {usedx[u] = 1;for(int i=1; i<=ny; i++){if(usedy[i] == 0){double t = bx[u] + by[i] - w[u][i];if(dcmp(t) == 0){usedy[i] = 1;if(cy[i] == -1 || dfs(cy[i])){cy[i] = u;cx[u] = i;return true;}}elseslack[i] = min(slack[i], t);}}return false; }void km() {mem(cx, -1);mem(cy, -1);mem(by, 0);for(int i=1; i<=n; i++){bx[i] = -INF;for(int j=1; j<=n; j++)bx[i] = max(bx[i], w[i][j]);}for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)slack[j] = INF;while(1){mem(usedx, 0);mem(usedy, 0);if(dfs(i)) break;double d = INF;for(int j=1; j<=n; j++)if(!usedy[j])d = min(d, slack[j]);for(int j=1; j<=n; j++)if(usedx[j] != 0) bx[j] -= d;for(int j=1; j<=n; j++)if(usedy[j] != 0) by[j] += d;else slack[j] -= d;}} }int main() {bool flag = true;while(~scanf("%d",&n)){if(true) flag = false;else printf("\n");for(int i=1; i<=n; i++){scanf("%lf%lf", &Node[i].x, &Node[i].y);}for(int i=1; i<=n; i++)scanf("%lf%lf", &Edge[i].x, &Edge[i].y);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)w[i][j] = -sqrt((Edge[i].x - Node[j].x)*(Edge[i].x - Node[j].x) + (Edge[i].y - Node[j].y)*(Edge[i].y - Node[j].y));nx = ny = n;km();for(int i=1; i<=n; i++)printf("%d\n", cy[i]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/WTSRUVF/p/9430756.html

總結(jié)

以上是生活随笔為你收集整理的Ants UVA - 1411（km板题竟然让我换了个板子）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。