保留道路
弄一个最小生成树。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m;
struct st{ll s,g;int x,y;
};
st a[50999];
st tmp[51999],tmp2[59899];
int f[59999],tot;int use[59999];ll ans=(1ll*1<<62),wg,wf;
bool cmp(st x,st y) {return x.s<y.s;
}
int find(int x){if(f[x]==x) return x;return f[x]=find(f[x]);
}
void getans(ll x){for(int i=1;i<=n;i++) f[i]=i;int j=0;ll p=0;for(int i=1;i<=tot;i++){tmp2[i]=tmp[i];use[i]=0;int fx=find(tmp2[i].x);int fy=find(tmp2[i].y);if(fx!=fy){j++;f[fx]=fy;p=max(p,tmp2[i].g);use[i]=1;}}if(j==n-1){ans=min(ans,x+p);int k=0;for(int i=1;i<=tot;i++)if(use[i])tmp[++k]=tmp2[i];tot=k;}
}
int main() {scanf("%d%d",&n,&m);scanf("%lld%lld",&wg,&wf);for(int i=1;i<=m;i++) {scanf("%d%d%lld%lld",&a[i].x,&a[i].y,&a[i].s,&a[i].g);a[i].s*=wg;a[i].g*=wf;}sort(a+1,a+m+1,cmp);for(int i=1;i<=m;i++){if(a[i].g+a[i].s>ans) continue;int w=tot+1;for(int j=1;j<=tot;j++){if(tmp[j].g<a[i].g) {w=j; break;}}if(w==tot+1){tmp[++tot]=a[i];}else{tot++;for(int j=tot;j>w;j--)tmp[j]=tmp[j-1];tmp[w]=a[i];}if(tot<n-1) continue;getans(a[i].s);}if(ans==(1ll*1<<62)) printf("-1");else printf("%lld",ans);
}三角形
把斜率相同的减除
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int a,b,c,ans,n,tot,maxn;double num[399999];
int main(){freopen("trokuti.in","r",stdin); freopen("trokuti.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);if(b!=0){ans++;num[i]=1.0*a/b;}else num[i]=99999999;}tot+=n*(n-1)*(n-2)/6;int w=0;sort(num+1,num+n+1);for(int i=1;i<=n;i++){//printf("%lf ",num[i]);if(num[i]!=num[i+1]){tot-=(i-w)*(i-w-1)/2*(n-(i-w));tot-=(i-w)*(i-w-1)*(i-w-2)/6;w=i;}}printf("%d",tot);
}