致远星
by nofall @ 2018-11-10 11:24:21
by L______ @ 2018-11-10 11:25:44
可能某谷认为P1000更简单
by WMDX @ 2018-11-10 11:26:46
```cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,maxn;
int a[500086];
int ans=0;
int main()
{
scanf("%d%d",&n,&a[1]);
maxn=a[1];
for(int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>maxn) a[1]+=a[i]-maxn;
maxn=a[i];
}
printf("%d",a[1]);
return 0;
}
```
by L______ @ 2018-11-10 17:25:00
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int T,n,ans=0,maxn=0,a[100+10];
bool vis[25000+10];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
maxn=0;ans=0;
memset(a,0,sizeof(a));
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxn=max(maxn,a[i]);
}
sort(a+1,a+n+1);
vis[0]=true;
for(int i=1;i<=n;i++)
{
if(vis[a[i]]==true) continue;
ans++;
for(int j=a[i];j<=maxn;j++)
{
vis[j]=vis[j]|vis[j-a[i]];
}
}
printf("%d\n",ans);
}
return 0;
}
```
by L______ @ 2018-11-10 17:25:12
# 致远星战况如何？
致远星战况如何？
by 谢hia @ 2018-11-22 18:45:28
```c
#include<cstdio>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,qx,qy,tx,ty;
int maps[210][210],book[210][210],f[210][210],s[210][210];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct node{
int x,y;
node(int a,int b) {x=a,y=b;}
};
void bfs(){
queue<node> q;
q.push(node(qx,qy));
while(!q.empty()){
int nx=q.front().x,ny=q.front().y;
q.pop();
for(int i=0;i<=3;i++){
int fx=nx+dx[i],fy=ny+dy[i];
if(fx<1||fx>n||fy<1||fy>m||maps[fx][fy]||s[fx][fy]<=s[nx][ny]) continue;
s[fx][fy]=s[nx][ny]+1;
f[fx][fy]+=f[nx][ny];
if(!book[fx][fy]){
book[fx][fy]=1;
q.push(node(fx,fy));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
maps[x][y]=1;
}
scanf("%d%d%d%d",&qx,&qy,&tx,&ty);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]=inf;
book[qx][qy]=true;f[qx][qy]=1;s[qx][qy]=0;
bfs();
if(s[tx][ty]>=inf) { printf("No Solution!\n");return 0;}
printf("%d\n%d\n",s[tx][ty],f[tx][ty]);
return 0;
}
```
by _Chris° @ 2019-01-23 13:35:30
```c
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=400000+12345;
int n,m,deep[N],f[N][28],Maxn[N][28],head[N],k,fa[N];bool vis[N];
long long ans;
struct ed{
int x,y,w;
bool f;
}a[N*3];
struct node{
int to,next,w;
}edg[N*6];
void build(int x,int y,int w){
edg[++k].to=y;edg[k].w=w;edg[k].next=head[x];head[x]=k;
}
bool cmp(ed a,ed b){return a.w<b.w;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kru(){int cnt=0,xx,yy;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
if(cnt==n-1)return;
xx=find(a[i].x);yy=find(a[i].y);
if(xx==yy)continue;
ans+=a[i].w;a[i].f=1;fa[xx]=yy;
build(a[i].x,a[i].y,a[i].w);
build(a[i].y,a[i].x,a[i].w);
}
}
void dfs(int u){
vis[u]=1;
for(int i=1;(1<<i)<=deep[u];i++){
f[u][i]=f[f[u][i-1]][i-1];
Maxn[u][i]=max(Maxn[u][i-1],Maxn[f[u][i-1]][i-1]);}
for(int i=head[u];i;i=edg[i].next){
int v=edg[i].to;
if(!vis[v]){//printf("%d %d\n",u,v);
deep[v]=deep[u]+1;
f[v][0]=u;Maxn[v][0]=edg[i].w;
dfs(v);
}
}
}
int LCA(int x,int y){
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;(1<<i)<=t;i++)if((1<<i)&t)x=f[x][i];
if(x==y)return x;
for(int i=27;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i],y=f[y][i];
}
}return f[x][0];
}
long long cx(int x,int y,int z){
if(deep[x]<deep[y])swap(x,y);
long long t=deep[x]-deep[y];
int tmp=-45;
for(int i=0;(1<<i)<=t;i++){
if(t&(1<<i)){
if(Maxn[x][i]<z)tmp=max(tmp,Maxn[x][i]);
//x=f[x][i];
}
}return tmp;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w),a[i].f=0;
kru();
deep[1]=1;dfs(1);long long s=ans;ans=2147483647000000;
for(int i=1;i<=m;i++){
if(a[i].f)continue;
int temp=LCA(a[i].x,a[i].y);
int p=max(cx(temp,a[i].x,a[i].w),cx(a[i].y,temp,a[i].w));
if(a[i].w>p)ans=min(ans,s-p+a[i].w);
}printf("%lld\n",ans);
return 0;
}
```
by 取名好烦人 @ 2019-02-16 12:01:31
```cpp
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100010
#define inf 9223372036854775807ll
#define int long long
using namespace std;
struct arr{
int x,y;
int s,g;
}a[maxn],b[maxn];
int n,m,ans,wg,ms,fa[maxn];
bool cmp(arr a,arr b){return a.s<b.s;}
bool cmp1(arr a,arr b){return a.g<b.g;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kru(int k)
{
for(int i=1;i<=n;i++) fa[i]=i;
int cnt=0;
for(int i=1;i<=n;i++)
{
int f1=find(b[i].x),f2=find(b[i].y);
if(f1!=f2)
{
fa[f1]=f2;
cnt++;
b[cnt]=b[i];
if(cnt==n-1)
{
ans=min(ans,a[k].s*ms+b[cnt].g*wg);
break;
}
}
}
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&wg,&ms);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].g,&a[i].s);
sort(a+1,a+1+m,cmp);
ans=inf;
for(int i=1;i<n;i++) b[i]=a[i];
sort(b+1,b+n,cmp1);
for(int k=n-1;k<=m;k++){
if(a[k].s*ms>=ans) break;
int lef=1,rig=n-1;
while(lef<rig){
int mid=(lef+rig)/2;
if(b[mid].g<a[k].g) lef=mid+1;
else rig=mid;
}
for(int i=n;i>lef;i--) b[i]=b[i-1];
b[lef]=a[k];
kru(k);
}
if(ans==inf) printf("-1");
else printf("%lld",ans);
}
```
by L______ @ 2019-02-16 20:10:41
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;int k=1;
struct node{
int fro,to,next;
int v;//最大载重
}edge[1000010];
int n,m,s,t;
int head[1000010];
void add(int u,int v,int w)
{
edge[++k].to=v;
edge[k].fro=u;
edge[k].v=w;
edge[k].next=head[u];
head[u]=k;
edge[++k].to=u;
edge[k].fro=v;
edge[k].v=0;
edge[k].next=head[v];
head[v]=k;
}
int deep[100010];
bool bfs()
{
memset(deep, 0, sizeof deep);
queue<int>q;
q.push(s);
deep[s]=1;
while(q.empty()==0)
{
int tem=q.front();q.pop();
for(int i=head[tem];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(deep[v]||edge[i].v<=0)continue;
deep[v]=deep[tem]+1;
q.push(v);
}
}
return deep[t];
}
int dfs(int u,int flow)//u点最大广增量(?),和到达u点最大能增光的值flow
{
if(u==t)return flow;
int add=0;//u点最大增广量
for(int i=head[u];i!=-1&&add<flow;i=edge[i].next)
{
int v=edge[i].to;
if(deep[v]!=deep[u]+1)continue;
if(!edge[i].v)continue;
int temadd=dfs(v,min(edge[i].v,flow-add));//到达u点最大值减去现在u点的值
edge[i].v-=temadd;
edge[i^1].v+=temadd;
add+=temadd;
}
return add;
}
int dic()
{
int ans=0;
while(bfs())
{
ans+=dfs(s,99999999);
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
printf("%d",dic());
return 0;
}
```
by GLZP @ 2019-02-17 21:26:45