「BZOJ1027」[JSOI2007] 合金
Description
某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。
Input
第一行两个整数m和n（m, n ≤ 500），分别表示原材料种数和用户需要的合金种数。第2到m + 1行，每行三个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m + n + 1行，每行三个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种用户需要的合金中所占的比重。
Output
一个整数，表示最少需要的原材料种数。若无解，则输出–1。
Sample Input
3 2
0.25 0.25 0.5
0 0.6 0.5
1 0 0
0.7 0.1 0.2
0.85 0.05 0.1
0.25 0.25 0.5
0 0.6 0.5
1 0 0
0.7 0.1 0.2
0.85 0.05 0.1
Sample Output
2
题解
好像是道很厉害的题
第三维可以由前两维确定，所以可以无视
两种原料能配成的产品一定在两点间线段
转化成在m个点里找最少点，围成的多边形包括了n个目标点
floyd求最小环。。。
具体就是如果目标点在线段a,b的一侧则dis[a][b]=1
否则dis[a][b]=inf
答案是min{dis[i][i]}
特判下所有点重合/共线
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 100000000 #define mod 1000000007 #define eps 1e-10 using namespace std; int n,m; struct P{ double x,y; }a[505],b[505]; int dis[505][505],mp[505][505]; double operator*(P a,P b) { return a.x*b.y-a.y*b.x; } P operator-(P a,P b) { P t;t.x=a.x-b.x;t.y=a.y-b.y;return t; } bool col(P x,P y) { if(x.x>y.x)swap(x,y); for(int i=1;i<=m;i++) if(b[i].x<x.x||b[i].x>y.x) return 0; if(x.y>y.y)swap(x,y); for(int i=1;i<=m;i++) if(b[i].y<x.y||b[i].y>y.y) return 0; return 1; } int jud(P x,P y) { int c1=0,c2=0; for(int i=1;i<=m;i++) { double t=(y-x)*(b[i]-x); if(t>eps)c1++; if(t<-eps)c2++; if(c1*c2)return 0; } if(!c1&&!c2&&col(x,y)){puts("2");return -1;} if(c1) return 1; if(c2) return 2; return 3; } void floyd() { int ans=inf; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(dis[i][k]<inf) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;i++)ans=min(ans,dis[i][i]); if(ans==inf||ans<=2)puts("-1"); else printf("%d",ans); } void solve() { for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int flag=jud(a[i],a[j]); if(flag==-1)return; if(flag==1)dis[i][j]=1; else if(flag==2)dis[j][i]=1; else if(flag==3)dis[i][j]=dis[j][i]=1; } floyd(); } bool spj() { for(int i=1;i<=n;i++) if(fabs(a[i].x-a[1].x)>eps||fabs(a[i].y-a[1].y)>eps)return 0; for(int i=1;i<=m;i++) if(fabs(b[i].x-a[1].x)>eps||fabs(b[i].y-a[1].y)>eps)return 0; puts("1"); return 1; } int main() { memset(dis,127/3,sizeof(dis)); scanf("%d%d",&n,&m); double K; for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&K); for(int i=1;i<=m;i++) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&K); if(spj())return 0; solve(); return 0; } |
计数器 9854144
OI 课件=>
OI 课件=>
卡掉了啊。。
5 1
0.6 0.3 0.1
0.6 0.3 0.1
0.6 0.3 0.1
0.6 0.3 0.1
0.2 0.1 0.1
0.6 0.3 0.1
黄学长您试一下这组数据会WA= =
4 1
0.5 0 0.5
0.5 0.25 0.25
0.4 0.4 0.2
0.6 0.4 0
0.5 0.3 0.2
答案是3，您的输出是-1
黄学长音乐能不能换一下？
竹取飞翔后面突然画风不对了2333
是IOSYS的锅
代码中
if(c1)return 1;
if(c2)return 2;
应为
if (!c2) return 1;
if (!c1) return 2;
错了啊 这样 return 3 没用了， 共线但不在两点之间的情况没有了
我交了一下都A啦 QWQ