usaco /the first wave

时间：2022-11-04 21:54:38

bzoj1572:贪心。先按时间顺序排序，然后用优先队列，如果时间不矛盾直接插入，否则判断队列中w最小的元素是否替换掉。（没用llWA了一次

#include<cstdio>

#include<cstring>

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ll long long

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=100005;

struct Node{

	int num,w;

	bool operator<(const Node&rhs)const{

	  return num<rhs.num;}

};

Node Nodes[nmax];

struct node{

	int num,w;

	bool operator<(const node&rhs)const{

	  return w>rhs.w;}

};

node nodes[nmax];

priority_queue<node>q;

int main(){

	int n=read();

	REP(i,1,n) Nodes[i].num=read(),Nodes[i].w=read();

	sort(Nodes+1,Nodes+n+1);

	REP(i,1,n) nodes[i].num=Nodes[i].num,nodes[i].w=Nodes[i].w;

	REP(i,1,n){

		node o=nodes[i];

		if(o.num>q.size()) {

			q.push(o);continue;

		}

		node tp=q.top();

		if(tp.w<o.w) q.pop(),q.push(o);

	}

	ll ans=0;

	while(!q.empty()) ans+=q.top().w,q.pop();

	printf("%lld\n",ans);

	return 0;

}

bzoj1574：贪心，将不能到达的点与相连的点集删除，然后dfs。（两个数组名相同RE了一次

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define qwq(x) for(edge *o=head[x];o;o=o->next)

#define op() clr(head,0);pt=edges;

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=30005;

const int maxn=200005;

struct edge{

	int to;edge *next;

};

edge edges[maxn],*pt,*head[nmax];

bool vis[nmax],V[nmax];

void adde(int u,int v){

	pt->to=v;pt->next=head[u];head[u]=pt++;

	pt->to=u;pt->next=head[v];head[v]=pt++;

}

void dfs(int x){

	V[x]=true;

	qwq(x) if(vis[o->to]&&!V[o->to]) dfs(o->to);

}

int main(){

	op();clr(vis,true);clr(V,false);

	int N=read(),M=read(),P=read(),u,v;

	REP(i,1,M) u=read(),v=read(),adde(u,v);

	REP(i,1,P) {

		u=read();vis[u]=false;

		qwq(u) vis[o->to]=false;

    }

	dfs(1);

	int ans=N;

	REP(i,1,N) if(V[i]) ans--;

	printf("%d\n",ans);

	return 0;

}

bzoj1576：由于最短路唯一。所以有最短路径树。未在树中的边u,v对于lca（u，v）以下的点，有dist[x]=dist[u]+dist[v]+val[u,v]-dist[x]（与dist[x]无关。可以将dist[u]+dist[v]+val[u,v]排序，依次更新。由于先更新的必定更优，于是可以用并查集压缩路径。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define qwq(x) for(edge *o=head[x];o;o=o->next)

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=100005;

const int maxn=400005;

const int inf=0x7f7f7f7f;

struct edge{

	int to,dist;edge *next;

};

edge edges[maxn],*pt,*head[nmax];

int d[nmax],dep[nmax],fa[nmax],ans[nmax];

void adde(int u,int v,int d){

	pt->to=v;pt->dist=d;pt->next=head[u];head[u]=pt++;

	pt->to=u;pt->dist=d;pt->next=head[v];head[v]=pt++;

}

struct node{

	int x,d;

	node(int x,int d):x(x),d(d){}

	bool operator<(const node&rhs) const{

	  return d>rhs.d;}

};

priority_queue<node>q;

void dijkstra(){

	clr(d,0x7f);d[1]=0;dep[1]=0;

	q.push(node(1,0));

	while(!q.empty()){

		node tmp=q.top();q.pop();

		if(d[tmp.x]!=tmp.d) continue;

		qwq(tmp.x) if(d[o->to]>d[tmp.x]+o->dist){

			d[o->to]=d[tmp.x]+o->dist;

			dep[o->to]=dep[tmp.x]+1;fa[o->to]=tmp.x;

			q.push(node(o->to,d[o->to]));

		}

	}

}

struct zc{

	int from,to,dist;

	bool operator<(const zc&rhs) const{

	  return dist<rhs.dist;}

};

zc zcs[maxn];

void getdep(int x){

}

int update(int u,int v,int val){

	if(u==v) return u;

	if(dep[u]<dep[v]) swap(u,v);

	if(ans[u]==-1) ans[u]=val-d[u];

	return fa[u]=update(fa[u],v,val);

}

int main(){

	clr(head,0);pt=edges;

	int N=read(),M=read(),u,v,dd;

	REP(i,1,M) {

		u=read(),v=read(),dd=read(),adde(u,v,dd);

		zc &oo=zcs[i];oo.from=u,oo.to=v,oo.dist=dd;

	}

	dijkstra();

	REP(i,1,N) printf("%d:%d\n",i,dep[i]);

	int cnt=0;

	REP(i,1,M) {

		zc &oo=zcs[i];

		if(d[oo.from]==d[oo.to]+oo.dist||d[oo.to]==d[oo.from]+oo.dist) continue;

		zc &ee=zcs[++cnt];

		ee.from=oo.from,ee.to=oo.to,ee.dist=d[oo.from]+d[oo.to]+oo.dist;

	}

	sort(zcs+1,zcs+cnt+1);

	clr(ans,-1);

	REP(i,1,cnt) update(zcs[i].from,zcs[i].to,zcs[i].dist);

	REP(i,2,N) printf("%d\n",ans[i]);

	return 0;

}

bzoj1585：建图后最小割就可以了。（由于没有处理第一个点的情况WA了一次

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t)  for(int i=s;i<=t;i++)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=10005;

const int maxn=200005;

const int inf=0x7f7f7f7f;

struct edge{

	int to,cap;edge *next,*rev;

};

edge edges[maxn],*pt,*head[nmax],*cur[nmax],*p[nmax];

void add(int u,int v,int d){

	pt->to=v;pt->cap=d;pt->next=head[u];head[u]=pt++;

}

void adde(int u,int v,int d){

	add(u,v,d);add(v,u,0);head[u]->rev=head[v];head[v]->rev=head[u];

}

int cnt[nmax],h[nmax];

int maxflow(int s,int t,int n){

	clr(cnt,0);cnt[0]=n;clr(h,0);

	int flow=0,a=inf,x=s;edge *e;

	while(h[s]<n){

		for(e=cur[x];e;e=e->next)  if(e->cap>0&&h[x]==h[e->to]+1) break;

		if(e){

			a=min(a,e->cap);cur[x]=p[e->to]=e;x=e->to;

			if(x==t){

				while(x!=s) p[x]->cap-=a,p[x]->rev->cap+=a,x=p[x]->rev->to;

				flow+=a,a=inf;

			}

		}else{

			if(!--cnt[h[x]]) break;

			h[x]=n;

			for(e=head[x];e;e=e->next) if(e->cap>0&&h[x]>h[e->to]+1) h[x]=h[e->to]+1,cur[x]=e;

			cnt[h[x]]++;

			if(x!=s) x=p[x]->rev->to;

		}

	}

	return flow;

}

bool vis[nmax];

int main(){

	clr(head,0);pt=edges;clr(vis,false);

	int N=read(),M=read(),P=read(),s=0,t=N+N+1;

	adde(s,1,inf);

	REP(i,1,M){

		int u=read(),v=read();

		adde(u+u,v+v-1,inf);adde(v+v,u+u-1,inf);

	}

	REP(i,1,P){

		int u=read();vis[u]=true;

	}

	adde(1,2,inf);

	REP(i,2,N){

		if(vis[i]) adde(i+i-1,i+i,inf),adde(i+i,t,inf);

		else adde(i+i-1,i+i,1);

	}

	printf("%d\n",maxflow(s,t,t+1));

	return 0;

}

bzoj1589：tarjan缩点后乱搞即可。（读入优化x=x*1+c-'0',由于自己出的都是小数据所以没有发现WA了一次。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<stack>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define qwq(x) for(edge *o=head[x];o;o=o->next)

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=200005;

const int maxn=400005;

const int inf=0x7f7f7f7f;

struct edge{

	int to;edge *next;

};

edge edges[maxn],*pt,*head[nmax];

void add(int u,int v){

	pt->to=v;pt->next=head[u];head[u]=pt++;

}

int sccno[nmax],scc[nmax],pre[nmax],scc_cnt,dfs_clock=0;

stack<int>s;

int dfs(int x){

	int lowu=pre[x]=++dfs_clock;

	s.push(x);

	qwq(x){

		int to=o->to;

		if(!pre[to]) lowu=min(lowu,dfs(to));

		else if(!sccno[to]) lowu=min(lowu,pre[to]);

	}

	if(lowu==pre[x]){

		scc_cnt++;scc[scc_cnt]=0;

		while(1){

			int tmp=s.top();s.pop();

			sccno[tmp]=scc_cnt;scc[scc_cnt]++;

			if(tmp==x) break;

		}

	}

	return lowu;

}

int sum[nmax];

int getsum(int x){

	if(sum[x]) return sum[x];

	int ans=scc[x];

	qwq(x) ans+=getsum(o->to);

	return ans;

}

int main(){

	clr(head,0);pt=edges;

	int N=read(),u;

	REP(i,1,N) u=read(),add(i,u);

	scc_cnt=N;

	REP(i,1,N) if(!pre[i]) dfs(i);

	REP(i,1,N) qwq(i) if(sccno[i]!=sccno[o->to]) add(sccno[i],sccno[o->to]);

	REP(i,N+1,scc_cnt) sum[i]=getsum(i);

	REP(i,1,N) printf("%d\n",sum[sccno[i]]);

	return 0;

}

summary：

1.各种神奇的错误方式。。。

2.自己出的数据也不要太小。。。但也不要自己被自己出的数据绕晕了。。。

相关文章