NC247069. 233的物品
描述
输入描述
第一行一个正整数
接下来行每行
个正整数代表
,保证
之间互不相同
输出描述
输出
示例1
输入:
4 6 2 3 7 2 3 30 5 3 42 6 3
输出:
42 21 -1 -1
示例2
输入:
3 6 2 3 150 5 4 156450 5 1
输出:
30 38 -1
C++(g++ 7.5.0) 解法, 执行用时: 38ms, 内存消耗: 1876K, 提交时间: 2022-12-09 22:06:19
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 510, M = 1e6 + 1;
int prime[M], len;
bool notprime[M] = {1, 1};
int nn, n, m, s, t, deg[N];
struct node{
int a, b, c;
} nd[N], le[N], ri[N];
int head[N], nxt[M], to[M], c[M], eid = 2;
long long w[M];
void addedge(int u, int v, int cc, long long ww){
to[eid] = v;
c[eid] = cc;
w[eid] = ww;
nxt[eid] = head[u];
head[u] = eid++;
}
long long d[N];
int p[N], q[N], l, r;
bool inq[N];
bool spfa(int s, int t){
memset(d, 0xc0, sizeof(d));
d[s] = 0;
l = r = 0;
q[r++] = s;
inq[s] = true;
while(l != r){
int i = q[l++];
l %= N;
inq[i] = false;
for(int e = head[i]; e; e = nxt[e])
if(c[e] && d[i] + w[e] > d[to[e]]){
d[to[e]] = d[i] + w[e];
p[to[e]] = e;
if(!inq[to[e]]){
q[r++] = to[e];
r %= N;
inq[to[e]] = true;
}
}
}
return d[t] > 0;
}
long long ans[4][N];
long long sum;
void solve(int type){
n = 0, m = 0;
eid = 2;
memset(head, 0, sizeof(head));
memset(deg, 0, sizeof(deg));
for (int i = 1; i <= nn; i++){
if(nd[i].a == 150){
if(type & 1)
le[++n] = nd[i];
else
ri[++m] = nd[i];
continue;
}
if(nd[i].a == 294){
if(type & 2)
le[++n] = nd[i];
else
ri[++m] = nd[i];
continue;
}
if(notprime[nd[i].a & (nd[i].a >> 1)]){
ri[++m] = nd[i];
}
else{
le[++n] = nd[i];
}
}
s = n + m + 1;
t = n + m + 2;
for (int i = 1; i <= n; i++){
addedge(s, i, 1, 0);
addedge(i, s, 0, 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
if(ri[j].a % (1ll * le[i].a * (le[i].a - 1)) == 0){
deg[j]++;
addedge(i, n + j, 1, 0);
addedge(n + j, i, 0, 0);
}
}
for (int i = 1; i <= m; i++){
int thre = min(deg[i], ri[i].b / ri[i].c);
int tmp = ri[i].b;
while(thre--){
long long w = 1ll * tmp * tmp - 1ll * (tmp - ri[i].c) * (tmp - ri[i].c);
addedge(n + i, t, 1, w);
addedge(t, n + i, 0, -w);
tmp -= ri[i].c;
}
}
long long del = 0;
bool flag = true;
for (int i = 1; i <= n + m; i++){
flag = flag && spfa(s, t);
if(flag){
int flow = 0x3f3f3f3f;
for(int i = t; i != s; i = to[p[i] ^ 1])
flow = min(flow, c[p[i]]);
for(int i = t; i != s; i = to[p[i] ^ 1]){
c[p[i]] -= flow;
c[p[i] ^ 1] += flow;
del += w[p[i]] * flow;
}
ans[type][i] = sum - del;
}
else
ans[type][i] = -1;
}
}
int main(){
for (int i = 2; i < M; i++){
if(!notprime[i])
prime[++len] = i;
for (int j = 1; j <= len && i * prime[j] < M; j++){
notprime[i * prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
scanf("%d", &nn);
for (int i = 1; i <= nn; i++){
scanf("%d%d%d", &nd[i].a, &nd[i].b, &nd[i].c);
sum += 1ll * nd[i].b * nd[i].b;
}
for (int i = 0; i < 4; i++)
solve(i);
for (int i = 1; i <= nn; i++){
long long res = 0x7fffffffffffffff;
for (int j = 0; j < 4; j++)
if(ans[j][i] != -1)
res = min(res, ans[j][i]);
printf("%lld\n", res == 0x7fffffffffffffff ? -1 : res);
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 80ms, 内存消耗: 1908K, 提交时间: 2022-12-13 15:02:50
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 5000000000000000ll
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define P 1000000007ll
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define sq sqrt
#define l(w) t[w].l
#define r(w) t[w].r
#define m(w) t[w].m
#define mn(w) t[w].mn
#define c(w) t[w].c
#define s(w) t[w].s
#define tag(w) t[w].tag
#define S second
#define mod 1000000007
#define sc(A) scanf("%d",&A)
#define scs(A) scanf("%s",A);
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define zz p<<1
#define yy p<<1|1
using namespace std;
const int MAXN=510,maxn=MAXN*MAXN<<1;
int n,len,S,T,SS;
int op[MAXN],vis[MAXN];
int a[MAXN],b[MAXN],c[MAXN],d[MAXN],in[MAXN],pre[MAXN];
ll ans[MAXN],dis[MAXN],res;
int lin[MAXN],ver[maxn],nex[maxn],e[maxn];ll e1[maxn];
inline void add(int x,int y,int z,ll z1)
{
ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=z;e1[len]=z1;
ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=0;e1[len]=-z1;
}
inline int pd(int x)
{
if(x==0||x==1)return 0;
for(int i=2;i*i<=x;++i)if(x%i==0)return 0;
return 1;
}
int q[maxn];
inline int spfa()
{
rep(1,T,i)dis[i]=INF;
int l=0,r=0;
q[++r]=S;dis[S]=0;in[S]=520;
while(++l<=r)
{
int x=q[l];vis[x]=0;
go(x)
{
if(!e[i])continue;
if(dis[x]+e1[i]<dis[tn])
{
dis[tn]=dis[x]+e1[i];
in[tn]=min(in[x],e[i]);
pre[tn]=i;
if(!vis[tn])q[++r]=tn,vis[tn]=1;
}
}
}
return dis[T]!=INF;
}
inline void EK()
{
int x=T,i;
res+=dis[T]*in[T];
while(x!=S)
{
i=pre[x];
e[i]-=in[T];
e[i^1]+=in[T];
x=ver[i^1];
}
}
inline void solve(int x)
{
len=1;ll cc=0;res=0;
rep(1,T,i)
{
b[i]=d[i];
if(a[i]==150)op[i]=x&1;
if(a[i]==294)op[i]=x&2;
lin[i]=0;
}
add(S,SS,0,0);
int kk=0;
rep(1,n,i)
{
cc+=(ll)b[i]*b[i];
if(op[i])
{
add(SS,i,1,0);
rep(1,n,j)
{
if(!op[j]&&a[j]%((ll)a[i]*a[i]-a[i])==0)
add(i,j,1,0);
}
++kk;
}
}
rep(1,n,i)
{
if(!op[i])
{
for(int j=1;j<=kk;++j)
if(b[i]>=c[i])
{
add(i,T,1,-((ll)b[i]*b[i]-(ll)(b[i]-c[i])*(b[i]-c[i])));
b[i]-=c[i];
}
else break;
}
}
rep(1,n,i)
{
++e[2];
if(spfa())
{
EK();
ans[i]=min(ans[i],res+cc);
}
else break;
}
}
int main()
{
//freopen("1.in","r",stdin);
sc(n);S=n+1;SS=S+1;T=SS+1;
rep(1,n,i)
{
sc(a[i]);sc(b[i]);sc(c[i]);d[i]=b[i];
ans[i]=INF;
if(a[i]<=1000&&pd(a[i]&(a[i]>>1)))op[i]=1;
}
solve(0);solve(1);solve(2);solve(3);
rep(1,n,i)
{
if(ans[i]==INF)puts("-1");
else putl(ans[i]);
}
return 0;
}