[Problem Description] 隨著社會的不斷發(fā)展，人與人之間的感情越來越功利化。最近，愛神丘比特發(fā)現(xiàn)，愛情也已不再是完全純潔的了。這使得丘比特很是苦惱，他越來越難找到合適的男女，并向他們射去丘比特之箭。于是丘比特千里迢迢遠(yuǎn)赴中國，找到了掌管東方人愛情的神——月下老人，向他求教。 月下老人告訴丘比特，純潔的愛情并不是不存在，而是他沒有找到。在東方，人們講究的是緣分。月下老人只要做一男一女兩個泥人，在他們之間連上一條紅線，那么它們所代表的人就會相愛——無論他們身處何地。而丘比特的愛情之箭只能射中兩個距離相當(dāng)近的人，選擇的范圍自然就小了很多，不能找到真正的有緣人。 丘比特聽了月下老人的解釋，茅塞頓開，回去之后用了人間的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。這樣，射中有緣人的機(jī)會也增加了不少。 情人節(jié)(Valentine's day)的午夜零時，丘比特開始了自己的工作。他選擇了一組數(shù)目相等的男女，感應(yīng)到他們互相之間的緣分大小，并依此射出了神箭，使他們產(chǎn)生愛意。他希望能選擇最好的方法，使被他選擇的每一個人被射中一次，且每一對被射中的人之間的緣分的和最大。 當(dāng)然，無論丘比特怎么改造自己的弓箭，總還是存在缺陷的。首先，弓箭的射程盡管增大了，但畢竟還是有限的，不能像月下老人那樣，做到“千里姻緣一線牽”。其次，無論怎么改造，箭的軌跡終歸只能是一條直線，也就是說，如果兩個人之間的連線段上有別人，那么莫不可向他們射出丘比特之箭，否則，按月下老人的話，就是“亂點(diǎn)鴛鴦譜”了。 作為一個凡人，你的任務(wù)是運(yùn)用先進(jìn)的計(jì)算機(jī)為丘比特找到最佳的方案。 [Algorithm] KM [Analysis] 接近裸題…… [Pay Attention] 1.讀入的名字是不區(qū)分大小寫的，所以做的時候要先將字符串全部轉(zhuǎn)換為大寫或者小寫 2.當(dāng)判斷兩個人之間無法連線時，應(yīng)該將它們之間的邊的權(quán)值設(shè)為-INF而不是0！ [Code] /**************************************************************Problem: 2539User: gaotianyu1350Language: C++Result: AcceptedTime:32 msMemory:1288 kb ****************************************************************/#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <map> using namespace std;const int MAXN = 40;bool luse[MAXN], ruse[MAXN]; int result[MAXN], l[MAXN], r[MAXN], slack[MAXN]; int gap[MAXN][MAXN]; int n, dis, x[MAXN * 2], y[MAXN * 2]; map<string, int> toname;void strrupr(char * s) {for (int i = 0; i < strlen(s); i++)if ('a' <= s[i] && s[i] <= 'z'){s[i] = 'A' + s[i] - 'a';} }bool find(int x) {luse[x] = true;for (int i = 1; i <= n; i++)if (!ruse[i]){int temp = l[x] + r[i] - gap[x][i];if (!temp){ruse[i] = true;if (!result[i] || find(result[i])){result[i] = x;return true;}}elseslack[i] = min(slack[i], temp);}return false; }inline int km() {memset(result, 0, sizeof(result));memset(l, 0, sizeof(l));memset(r, 0, sizeof(r));for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)l[i] = max(l[i], gap[i][j]);for (int i = 1; i <= n; i++) {memset(slack, 0x7f, sizeof(slack));while (1){memset(luse, 0, sizeof(luse));memset(ruse, 0, sizeof(ruse));if (find(i)) break;int minn = 1000000000;for (int i = 1; i <= n; i++)if (!ruse[i])minn = min(minn, slack[i]);for (int i = 1; i <= n; i++){if (luse[i]) l[i] -= minn;if (ruse[i]) r[i] += minn;else slack[i] -= minn;}}}int sum = 0;for (int i = 1; i <= n; i++)sum += l[i] + r[i];return sum; }inline void init() {int xmin, xmax, ymin, ymax;for (int i = 1; i <= n; i++)for (int j = n + 1; j <= n * 2; j++){if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) > dis * dis){gap[i][j - n] = -1000000000;continue;}for (int k = 1; k <= n * 2; k++)if (k != i && k != j){xmin = min(x[i], x[j]);ymin = min(y[i], y[j]);xmax = max(x[i], x[j]);ymax = max(y[i], y[j]);if (xmin <= x[k] && x[k] <= xmax && ymin <= y[k] && y[k] <= ymax &&(y[k] - y[i]) * (x[j] - x[i]) == (y[j] - y[i]) * (x[k] - x[i])){gap[i][j - n] = -1000000000;break;}}} }int main() {//freopen("input.txt", "r", stdin);scanf("%d%d", &dis, &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)gap[i][j] = 1;toname.clear();string strName;char lpszName[100];for (int i = 1; i <= n; i++){scanf("%d%d%s", &x[i], &y[i], lpszName);strrupr(lpszName);strName = lpszName;toname[strName] = i;}for (int i = n + 1; i <= n * 2; i++){scanf("%d%d%s", &x[i], &y[i], lpszName);strrupr(lpszName); strName = lpszName;toname[strName] = i;}while (1){scanf("%s", lpszName);strrupr(lpszName);strName = lpszName;if (strName == "END") break;int theX = toname[strName];scanf("%s", lpszName);strrupr(lpszName);strName = lpszName;int theY = toname[strName];int temp;scanf("%d", &temp);if (theX > theY){int t = theX; theX = theY; theY = t;}gap[theX][theY - n] = temp;}init();printf("%d\n", km()); }

總結(jié)

以上是生活随笔為你收集整理的[BZOJ2539][CTSC2000][KM]丘比特的烦恼的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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