41 条题解
-
1
Sky1231 (sky1231) LV 10 @ 2017-06-22 18:55:41
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int s_l=20,n_p_r=1,oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,m; vector<int> l; vector<int> l_a; vector<int> l_b; vector<int> a_x; vector<int> a_y; vector<int> b_x; vector<int> b_y; vector<vector<int> > a_b_r; vector<bool> v_a; vector<bool> v_b; vector<string> a_s; vector<string> b_s; bool check_1(int a,int b) { if (pow(double(a_x[a]-b_x[b]),double(2))+pow(double(a_y[a]-b_y[b]),double(2))>pow(double(m),double(2))) return 0; for (int i=1;i<=n;i++) if (((a_x[a]<=a_x[i]&&a_x[i]<=b_x[b])||(b_x[b]<=a_x[i]&&a_x[i]<=a_x[a]))&&((a_y[a]<=a_y[i]&&a_y[i]<=b_y[b])||(b_y[b]<=a_y[i]&&a_y[i]<=a_y[a]))&&i!=a) { int a_i_x=a_x[i]-a_x[a],a_i_y=a_y[i]-a_y[a],i_b_x=b_x[b]-a_x[i],i_b_y=b_y[b]-a_y[i]; if (a_i_x*i_b_y-i_b_x*a_i_y==0) return 0; } for (int i=1;i<=n;i++) if (((a_x[a]<=b_x[i]&&b_x[i]<=b_x[b])||(b_x[b]<=b_x[i]&&b_x[i]<=a_x[a]))&&((a_y[a]<=b_y[i]&&b_y[i]<=b_y[b])||(b_y[b]<=b_y[i]&&b_y[i]<=a_y[a]))&&i!=b) { int a_i_x=b_x[i]-a_x[a],a_i_y=b_y[i]-a_y[a],i_b_x=b_x[b]-b_x[i],i_b_y=b_y[b]-b_y[i]; if (a_i_x*i_b_y-i_b_x*a_i_y==0) return 0; } return 1; } bool find_1(int now) { v_a[now]=1; for (int i=1;i<=n;i++) if (v_b[i]==0&&l_a[now]+l_b[i]==a_b_r[now][i]) { int temp=l[i]; l[i]=now,v_b[i]=1; if (temp>0) { if (find_1(temp)==1) return 1; } else return 1; l[i]=temp; } return 0; } int work_1() { l.resize(0); l.resize(n+1,0); l_a.resize(0); l_a.resize(n+1,0); l_b.resize(0); l_b.resize(n+1,0); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) l_a[i]=max(l_a[i],a_b_r[i][j]); for (int now=1;now<=n;now++) while (1) { v_a.resize(0); v_a.resize(n+1,0); v_b.resize(0); v_b.resize(n+1,0); if (find_1(now)==1) break; int d=(numeric_limits<int>::max)(); for (int i=1;i<=n;i++) if (v_a[i]==1) for (int j=1;j<=n;j++) if (v_b[j]==0) d=min(d,l_a[i]+l_b[j]-a_b_r[i][j]); for (int i=1;i<=n;i++) l_a[i]-=((v_a[i]==1)?d:0); for (int i=1;i<=n;i++) l_b[i]+=((v_b[i]==1)?d:0); } int ans=0; for (int i=1;i<=n;i++) ans+=a_b_r[l[i]][i]; return ans; } int main() { while (~scanf("%d%d",&m,&n)) { a_x.resize(0); a_x.resize(n+1,0); a_y.resize(0); a_y.resize(n+1,0); a_s.resize(0); a_s.resize(n+1); for (int i=1;i<=n;i++) { a_s[i].resize(0); a_s[i].resize(s_l,0); scanf("%d%d%s",&a_x[i],&a_y[i],&(a_s[i][0])); for (int j=0;j<a_s[i].size();j++) if ('A'<=a_s[i][j]&&a_s[i][j]<='Z') a_s[i][j]+='a'-'A'; } b_x.resize(0); b_x.resize(n+1,0); b_y.resize(0); b_y.resize(n+1,0); b_s.resize(0); b_s.resize(n+1); for (int i=1;i<=n;i++) { b_s[i].resize(0); b_s[i].resize(s_l,0); scanf("%d%d%s",&b_x[i],&b_y[i],&(b_s[i][0])); for (int j=0;j<b_s[i].size();j++) if ('A'<=b_s[i][j]&&b_s[i][j]<='Z') b_s[i][j]+='a'-'A'; } a_b_r.resize(0); a_b_r.resize(n+1); for (int i=1;i<=n;i++) a_b_r[i].resize(n+1,n_p_r); int p; string p_1_s,p_2_s,s_end="end"; p_1_s.resize(0); p_1_s.resize(s_l,0); p_2_s.resize(0); p_2_s.resize(s_l,0); s_end.resize(s_l,0); while (~scanf("%s",&(p_1_s[0]))) { for (int i=0;i<p_1_s.size();i++) if ('A'<=p_1_s[i]&&p_1_s[i]<='Z') p_1_s[i]+='a'-'A'; if (p_1_s!=s_end) { scanf("%s%d",&(p_2_s[0]),&p); for (int i=0;i<p_2_s.size();i++) if ('A'<=p_2_s[i]&&p_2_s[i]<='Z') p_2_s[i]+='a'-'A'; bool b=0; for (int i=1;i<=n&&b==0;i++) if (a_s[i]==p_1_s||a_s[i]==p_2_s) for (int j=1;j<=n&&b==0;j++) if ((a_s[i]==p_1_s&&b_s[j]==p_2_s)||(a_s[i]==p_2_s&&b_s[j]==p_1_s)) a_b_r[i][j]=p,b=1; p_1_s.resize(0); p_1_s.resize(s_l,0); p_2_s.resize(0); p_2_s.resize(s_l,0); } else break; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (check_1(i,j)==0) a_b_r[i][j]=oo_min;//不应该是0吗? printf("%d\n",work_1()); } }-
那个不应该是0吗？但是0会错第5个点
-
-
1
/* 二分图最优完美匹配 KM算法Orz 考虑到也就只有男的和女的两种人咯(难道还有双性？) 然后就很明显考虑到二分图咯 但是关键难点在于建图QAQ QWQ而且字符串处理也很麻烦(对于我这种弱弱来说233333) 但主要是判断两个人是否能连成一条边啊 要满足两个条件 1.要在射程范围内，这个就很简单，我们直接求出两个点的欧几里德距离就好了 没啥很大的难度 2.两个人的连线上不能有另外一个人 这个也不麻烦，因为n也就不超过30吧，直接暴力一点咯 枚举所有人判断是否在一条直线上 如果三个点在一条直线上，那么一定可以根据直角三角形之类的组成相似三角形咯 这个就自行脑补了我提供了一种判断的方法 那么理清了这个我们在处理好name后，然后对于每对点，如果满足这个我们就拉一条无向边 这样就成功地构成了一个二分图模型QAQ 然后就是求这个二分图的最优完美匹配了 嗯这个就是裸的KM算法了(原谅我不会网络流啊) 然后我用的是O(n^4)的KM算法啊 实际上是可以优化顶标查找使算法到O(n^3) Orz但是实际上这种图的最优匹配都是很好找的 所以O(n^4)比O(n^3)也慢不了多少 而且n也很小 所以偷个懒就写了个朴素的KM算法咯 也算是练习了一下KM算法了 一道好题~ 调了一中午QAQ 还要特别注意的一个地方 对于两者不能连线的情况 一定要将其权值设为-INF而不能是0 不然第五个点稳稳地爆炸啊 QAQ一定要小心细节 一个地方炸了全都炸 建议每写好一个部分就测试一下 确保无误再写下一部分 但还是有个小小的疑惑在心里 在处理边的时候 本来按道理是男的和女的才能连边？ 但是我直接男的和男的连边(标记的地方 把i,j的循环是对于所有n个点的) 结果也能AC 这不符合我的意志 这非常尴尬QAQ 留到以后来考虑吧 先去QAQ了 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=2000; const int INF=0x7fffff; struct node { int x,y; }a[MAXN]; int n,m,maxd; int w[MAXN][MAXN]; int lx[MAXN],ly[MAXN],slack[MAXN]; int s[MAXN],t[MAXN]; int match[MAXN]; int ans; string name[MAXN]; bool Dist(int n1,int n2) { return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x) +(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y))<=maxd; } bool Dir(int n1,int n2) { if(a[n1].x==a[n2].x) { for(int i=1;i<=n;i++) if(i!=n1&&i!=n2) if(a[i].x==a[n1].x) if(a[i].y<=max(a[n1].y,a[n2].y)) if(a[i].y>=min(a[n1].y,a[n2].y)) return false; return true; } else { for(int i=1;i<=n;i++) if(i!=n1&&i!=n2) if(a[i].x<=max(a[n1].x,a[n2].x)) if(a[i].x>=min(a[n1].x,a[n2].x)) if((a[n1].y-a[i].y)*(a[n2].x-a[i].x)== (a[n2].y-a[i].y)*(a[n1].x-a[i].x)) return false; return true; } } string change(string x) { int k=x.length(); for(int i=0;i<k;i++) if(x[i]>='A'&&x[i]<='Z') x[i]-=('A'-'a'); return x; } void init() { cin>>maxd>>n; n*=2; //for(int i=1;i<=n;i++) //for(int j=1;j<=n;j++) //w[i][j]=-INF; for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>name[i]; for(int i=1;i<=n;i++) name[i]=change(name[i]); string s1,s2; while(true) { cin>>s1; if(s1=="End") break; cin>>s2; s1=change(s1); s2=change(s2); int n1=0,n2=0; for(int i=1;i<=n;i++) if(name[i]==s1) { n1=i; break; } for(int i=1;i<=n;i++) if(name[i]==s2) { n2=i; break; } int k; cin>>k; if(Dist(n1,n2)&&Dir(n1,n2)) w[n1][n2]=w[n2][n1]=k; } for(int i=1;i<=n/2;i++) for(int j=n/2;j<=n;j++)//Orz不解 if(i!=j&&!w[i][j]) if(Dist(i,j)&&Dir(i,j)) w[i][j]=w[j][i]=1; //没有边相连就要设为-INF而不能为0！！！ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!w[i][j]) w[i][j]=-INF; } bool dfs(int x) { s[x]=1; for(int i=1;i<=n;i++) { if(lx[x]+ly[i]==w[x][i]&&!t[i]) { t[i]=1; if(!match[i]||dfs(match[i])) { match[i]=x; return true; } } } return false; } void update() { int a=INF; for(int i=1;i<=n;i++) if(s[i]) for(int j=1;j<=n;j++) if(!t[j]) a=min(a,lx[i]+ly[j]-w[i][j]); for(int i=1;i<=n;i++) { if(s[i]) lx[i]-=a; if(t[i]) ly[i]+=a; } } void KM() { memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); memset(match,0,sizeof(match)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) lx[i]=max(lx[i],w[i][j]); for(int i=1;i<=n;i++) for(;;) { memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); if(dfs(i)) break; else update(); } for(int i=1;i<=n;i++) ans+=w[i][match[i]]; cout<<ans/2<<endl; } int main() { init(); KM(); return 0; } -
0
楼上这么多说数据有问题需要cheat、“数据剪枝”的，实际上只有第5个点有毒，**需要注意的是，如果两个人不连通边不能放进图！不只是边权为0！**
测试数据 #0: Accepted, time = 15 ms, mem = 580 KiB, score = 10 测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10 测试数据 #2: Accepted, time = 0 ms, mem = 584 KiB, score = 10 测试数据 #3: Accepted, time = 0 ms, mem = 584 KiB, score = 10 测试数据 #4: Accepted, time = 0 ms, mem = 584 KiB, score = 10 测试数据 #5: Accepted, time = 15 ms, mem = 584 KiB, score = 10 测试数据 #6: Accepted, time = 0 ms, mem = 580 KiB, score = 10 测试数据 #7: Accepted, time = 0 ms, mem = 580 KiB, score = 10 测试数据 #8: Accepted, time = 15 ms, mem = 584 KiB, score = 10 测试数据 #9: Accepted, time = 0 ms, mem = 584 KiB, score = 10 Accepted, time = 45 ms, mem = 584 KiB, score = 100 -
0
suifen123456 LV 8 @ 2009-11-10 16:46:22
要注意的几点
1.弓箭的射程有限。
2.箭的轨迹只能是一条直线，两个人之间的连线段不能有别人。
3.忽略大小写的区别。
4.如果没有被描述，则说明他们缘分值为1。
5.不用完全匹配。
至于重边....是不是数据有问题...
交了N次...T_T -
0
...
做了两天，一直卡在No.5上
最后看题解，发现**第5个点居然是错的！！！**
附：No.5 data,请管理员仔细检查
Input:
36
10
2 -7 aa
-23 -22 ab
-5 -16 ac
9 14 ad
8 -13 ae
3 7 af
-9 9 ag
8 22 ah
-9 -22 ai
14 13 aj
18 1 ba
2 23 bb
-14 0 bc
-24 -19 bd
18 -12 be
19 5 bf
-20 -17 bg
18 -19 bh
20 -3 bi
1 -16 bj
AC BG 90
AH BA 40
AE BE 89
BF AB 153
BG AD 188
AJ BF 109
AI BG 172
AG BH 161
AF BD 142
BD AC 239
AC BB 24
AH BD 201
BD AE 171
AJ BH 149
BF AH 6
BE AE 75
AJ BD 56
AA BJ 85
AE BA 251
AJ BJ 200
BE AC 74
AA BI 231
AF BB 79
AF BI 251
AI BB 160
BH AJ 118
BJ AA 208
AA BC 105
BF AC 75
BA AB 76
AJ BA 127
AA BI 16
BG AD 98
AD BI 134
BE AC 56
AF BH 21
BE AI 179
BH AG 192
AE BH 99
AC BJ 122
AF BB 112
BE AD 202
BD AJ 168
AB BF 199
AC BE 223
BE AI 85
AG BF 154
AI BG 191
AF BG 13
AF BI 160
BB AC 106
AH BH 16
AH BF 123
BJ AD 47
BJ AG 150
BI AC 250
BB AB 209
AE BI 116
BE AG 154
AC BH 18
AE BH 139
AG BC 134
AA BA 159
BC AC 217
AB BG 170
AA BB 202
EndOutput:
1682答案应该是1702
-
0
lijian3256 LV 10 @ 2009-07-21 11:31:19
没用网上流传的KM算法 。对着算法导论敲。。。第十点无尽WA 比答案多6 额。。我太弱了 只好CHeat 抚慰下。。
关于第五个点的解释：最优解不一定在最大匹配的时候 形如
100 1
1 0
最大匹配情况下为2 而最优解为100 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
还是费用流实惠。注意大小写忽略。 -
0
czz5242199 LV 9 @ 2009-04-29 22:26:23
第100个AC，一个裸的KM算法
Flag Accepted
题号 P1169
类型(?) 其它
通过 100人
提交 480次
通过率 21%
难度 4编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
Sky1231 (sky1231)
LV 10
@ 2017-06-22 18:55:41
