290. [CTSC2000] 丘比特的煩惱

★★★?? 輸入文件：cupid.in?? 輸出文件：cupid.out???簡單對比
時(shí)間限制：1 s?? 內(nèi)存限制：128 MB

隨著社會的不斷發(fā)展，人與人之間的感情越來越功利化。最近，愛神丘比特發(fā)現(xiàn)，愛情也已不再是完全純潔的了。這使得丘比特很是苦惱，他越來越難找到合適的男女，并向他們射去丘比特之箭。于是丘比特千里迢迢遠(yuǎn)赴中國，找到了掌管東方人愛情的神——月下老人，向他求教。
月下老人告訴丘比特，純潔的愛情并不是不存在，而是他沒有找到。在東方，人們講究的是緣分。月下老人只要做一男一女兩個泥人，在他們之間連上一條紅線，那么它們所代表的人就會相愛——無論他們身處何地。而丘比特的愛情之箭只能射中兩個距離相當(dāng)近的人，選擇的范圍自然就小了很多，不能找到真正的有緣人。
丘比特聽了月下老人的解釋，茅塞頓開，回去之后用了人間的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。這樣，射中有緣人的機(jī)會也增加了不少。
情人節(jié)(Valentine's day)的午夜零時(shí)，丘比特開始了自己的工作。他選擇了一組數(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)，它們之間用空格分隔。格式為x y Name。輸入文件剩下的部分描述了這些人的緣分。每一行的格式為Name1 Name2 p。Name1和Name2為有緣人的姓名，p是他們之間的緣分值(p為小于等于255的正整數(shù))。以一個End作為文件結(jié)束標(biāo)志。每兩個人之間的緣分如果被描述多次，以最后一次為準(zhǔn)。如果沒有被描述，則說明他們緣分值為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

思路：先根據(jù)題目要求建圖，然后跑KM算法。

錯因：未知。不知道為什么就wa了。自測數(shù)據(jù)全部正確沒交上評測結(jié)果不相同。

KM算法的代碼。

#include<iostream> #include<map> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct nond{int x,y; }pe[70]; map<string,int>ma; int k,n,ans,love[70][70],vis_boy[70],slack[70]; int match[70],ex_boy[70],ex_girl[70],vis_girl[70]; int judge(char s[],char ss[],int x){int s1=ma[s],s2=ma[ss];int x1=pe[s1].x-pe[s2].x;int y1=pe[s1].y-pe[s2].y;if(x1*x1+y1*y1>k*k) return true;elsefor(int i=1;i<=2*n;i++){if(i==s1||i==s2) continue;int x2=pe[s1].x-pe[i].x;int y2=pe[s1].y-pe[i].y;if(x1*y2-x2*y1!=0) continue;if(pe[i].x>pe[s1].x&&pe[i].x<pe[s2].x&&pe[i].y>pe[s1].y&&pe[i].y<pe[s2].y||pe[i].x>pe[s2].x&&pe[i].x<pe[s1].x&&pe[i].y>pe[s2].y&&pe[i].y<pe[s1].y||pe[i].x>pe[s1].x&&pe[i].x<pe[s2].x&&pe[i].y>pe[s2].y&&pe[i].y<pe[s1].y||pe[i].x>pe[s2].x&&pe[i].x<pe[s1].x&&pe[i].y>pe[s1].y&&pe[i].y<pe[s2].y)return true;else return false;} } bool dfs(int girl){vis_girl[girl]=true;for(int boy=0;boy<n;boy++){if(vis_boy[boy]) continue;int now=ex_girl[girl]+ex_boy[boy]-love[girl][boy];if(now==0){vis_boy[boy]=true;if(match[boy]==-1||dfs(match[boy])){match[boy]=girl;return true;}}else slack[boy]=min(slack[boy],now);}return false; } int KM(){memset(match,-1,sizeof(match));memset(ex_boy,0,sizeof(ex_boy));for(int i=0;i<n;i++){ex_girl[i]=love[i][0];for(int j=1;j<n;j++)ex_girl[i]=max(ex_girl[i],love[i][j]);}for(int i=0;i<n;i++){memset(slack,0x3f3f3f3f,sizeof(slack));while(1){memset(vis_boy,0,sizeof(vis_boy));memset(vis_girl,0,sizeof(vis_girl));if(dfs(i)) break;int d=0x3f3f3f3f;for(int j=0;j<n;j++)if(!vis_boy[j]) d=min(d,slack[j]);for(int j=0;j<n;j++){if(vis_girl[j]) ex_girl[j]-=d;if(vis_boy[j]) ex_boy[j]+=d;else slack[j]-=d;}}}int rest=0;for(int i=0;i<n;i++)rest+=love[match[i]][i];return rest; } int main(){freopen("cupid.in","r",stdin);freopen("cupid.out","w",stdout);scanf("%d%d",&k,&n);for(int i=1;i<=2*n;i++){int x,y;char s[110];cin>>x>>y;cin>>s;for(int j=0;j<strlen(s);j++)if(s[j]>='A'&&s[j]<='Z') s[j]+=32;pe[i].x=x;pe[i].y=y;ma[s]=i;}char s[110],ss[110];int x;for(int i=0;i<n;i++)for(int j=0;j<n;j++)love[i][j]=1;while(cin>>s){if(s[0]=='E'&&s[1]=='n'&&s[2]=='d')break;cin>>ss>>x;for(int j=0;j<strlen(s);j++)if(s[j]>='A'&&s[j]<='Z') s[j]+=32;for(int j=0;j<strlen(ss);j++)if(ss[j]>='A'&&ss[j]<='Z') ss[j]+=32;if(!judge(s,ss,x)){int s1=ma[s];int s2=ma[ss];if(s2>n) swap(s1,s2);love[s1%n][s2%n]=x;}}ans=KM();cout<<ans;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/7423682.html

總結(jié)

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

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