題目描述

隨著社會的不斷發(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ī)為丘比特找到最佳的方案。

輸入格式

第一行為正整數(shù)k，表示丘比特之箭的射程， 第二行為正整數(shù)n(n<30)，隨后有2n行，表示丘比特選中的人的信息，其中前n行為男子，后n行為女子。每個 人的信息由兩部分組成：他的姓名和他的位置。姓名是長度小于20且僅包含字母的字符串，忽略大小寫的區(qū)別， 位置是由一對整數(shù)表示的坐標(biāo)，它們之間用空格分隔。格式為Name x y。 剩下的部分描述了這些人的緣分。 每一行的格式為Name1 Name2 p。Name1和Name2為有緣人的姓名，p是他們之間的緣分值(p為小于等于255的正 整數(shù))。以一個End作為文件結(jié)束標(biāo)志。每兩個人之間的緣分至多只被描述一次。如果沒有被描述，則說明他們 緣分值為1。

輸出格式

僅一個正整數(shù)，表示每一對被射中的人之間的緣分的總和。這個和應(yīng)當(dāng)是最大的。

樣例

樣例輸入

2 3 0 0 Adam 1 1 Jack 0 2 George 1 0 Victoria 0 1 Susan 1 2 Cathy Adam Cathy 100 Susan George 20 George Cathy 40 Jack Susan 5 Cathy Jack 30 Victoria Jack 20 Adam Victoria 15 End

樣例輸出

65

來源

ctsc2000

代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #include<cstring> #include<string> #define MAXN 100 #define MAX 999999999 using namespace std; int n,k,c=2,s,t,maxcost=0; int head[MAXN],path[MAXN],fa[MAXN],deep[MAXN],g[MAXN][MAXN]; bool vis[MAXN]; string name[MAXN]; struct node1{int next,to,w,cost; }a[MAXN*MAXN]; struct node2{int x,y; }b[MAXN]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline int relax(int u,int v,int i,int cost){if(path[v]<path[u]+cost){path[v]=path[u]+cost;fa[v]=u;deep[v]=i;return 1;}return 0; } inline void add(int u,int v,int w,int cost){a[c].to=v;a[c].w=w;a[c].cost=cost;a[c].next=head[u];head[u]=c++;a[c].to=u;a[c].w=0;a[c].cost=-cost;a[c].next=head[v];head[v]=c++; } bool spfa(){int u,v;queue<int> q;for(int i=s;i<=t;i++){path[i]=-MAX;vis[i]=false;}path[s]=0;vis[s]=true;q.push(s);while(!q.empty()){u=q.front();q.pop();vis[u]=false;for(int i=head[u];i;i=a[i].next){v=a[i].to;if(a[i].w&&relax(u,v,i,a[i].cost)&&!vis[v]){vis[v]=true;q.push(v);}}}if(path[t]==-MAX)return false;for(int i=t;i!=s;i=fa[i]){a[deep[i]].w--;a[deep[i]^1].w++;}return true; } void EK(){while(spfa())maxcost+=path[t]; } inline double dis(int i,int j){return sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y)); } void change(string &s){for(int i=0;i<s.length();i++)if(s[i]>='A'&&s[i]<='Z')s[i]=s[i]-'A'+'a'; } bool check(int i,int j){if(dis(i,j)>k)return false;for(int k=1;k<=2*n;k++){if(k==i||k==j)continue;if(dis(i,k)+dis(k,j)-dis(i,j)<0.000001)return false;}return true; } int main(){string ch1,ch2;int x,y,z;k=read();n=read();s=0;t=2*n+1;for(int i=1;i<=2*n;i++){b[i].x=read();b[i].y=read();cin>>name[i];change(name[i]);}for(int i=1;i<=n;i++){add(s,i,1,0);add(i+n,t,1,0);}while(1){cin>>ch1;if(ch1=="End")break;cin>>ch2;z=read();change(ch1);change(ch2);for(int i=1;i<=2*n;i++){if(ch1==name[i])x=i;if(ch2==name[i])y=i;}if(x>y)swap(x,y);g[x][y]=g[y][x]=z;}for(int i=1;i<=n;i++)for(int j=n+1;j<=n*2;j++)if(check(i,j))add(i,j,1,g[i][j]==0?1:g[i][j]);EK();printf("%d\n",maxcost);return 0; }

總結(jié)

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

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