NOI2010 海拔

本文主要是介绍NOI2010 海拔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正解是平面图转对偶图 然后跑最短路

先是题目的读入 没有说明白 导致wa

后来用最大流最小割TLE后两个点

转SPFA跑最短路 依然TLE后两个点

SPFA加上优先队列优化 才A掉

貌似更多人写heap优化的dijkstra....

注意最短路建图 由于每条边是双向的 所以一一对应到最短路的边权里去

自己画下图就能发现怎么对应

80分的最大流:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;int id[600][600],cnt;
const int MAXN=2*2*2*600*(500+1)+100;
int tot=1,g[MAXN],nnext[MAXN],flow[MAXN],num[MAXN];
void add(int x,int y,int z)
{tot++;nnext[tot]=g[x];g[x]=tot;num[tot]=y;flow[tot]=z;
}
void ADD(int x,int y,int z)
{add(x,y,z);add(y,x,0);
}int d[MAXN],team[MAXN],head,tail;
int s,t;
bool bfs()
{memset(d,0,sizeof(d));head=tail=0;team[++tail]=s;d[s]=1;while(head<tail){int x=team[++head];for(int i=g[x];i;i=nnext[i]){int tmp=num[i];if(flow[i]&&d[tmp]==0){d[tmp]=d[x]+1;team[++tail]=tmp;}}}if(d[t]==0) return 0;return true;
}int dfs(int x,int mmin)
{if(x==t) return mmin;int f=0,tmp;for(int i=g[x];i;i=nnext[i]){if(d[num[i]]==d[x]+1&&flow[i]&&(tmp=dfs(num[i],min(flow[i],mmin)))){flow[i]-=tmp;flow[i^1]+=tmp;f+=tmp;mmin-=tmp;if(mmin==0){return f;}}}d[x]=0;return f;
}int main()
{int n;cin>>n;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)id[i][j]=++cnt;for(int j=0;j<=n;j++)for(int i=1;i<=n;i++)	{int x;scanf("%d",&x);ADD(id[j][i-1],id[j][i],x);}	for(int j=1;j<=n;j++)for(int i=0;i<=n;i++){int x;scanf("%d",&x);ADD(id[j-1][i],id[j][i],x);}	for(int j=0;j<=n;j++)for(int i=1;i<=n;i++){int x;scanf("%d",&x);ADD(id[j][i],id[j][i-1],x);}for(int j=1;j<=n;j++)for(int i=0;i<=n;i++)	{int x;scanf("%d",&x);ADD(id[j][i],id[j-1][i],x);}s=id[0][0];t=id[n][n];int ans=0;while(bfs()) ans+=dfs(s,2e9);cout<<ans<<endl;return 0;
}

100分的SPFA:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int MAXN = 4*500+500*500+10;
const int MAXM = 4*500*(500+1)+10;int n,s,t,cnt=0;
int dis[MAXN];
int id[502][502];
bool in[MAXN];int tot,g[MAXN],nnext[MAXM],num[MAXM],cost[MAXM];
void add(int x,int y,int z){tot++;nnext[tot]=g[x];g[x]=tot;num[tot]=y;cost[tot]=z;}struct H
{int x;bool operator < (const H b)const {return dis[x]>dis[b.x];}
};
priority_queue <H> q;int SPFA()
{memset(dis,100,sizeof(dis));q.push((H){s});in[s]=true;dis[s]=0;while(q.size()){int x=q.top().x;q.pop();in[x]=false;for(int i=g[x];i;i=nnext[i]){if(dis[num[i]]>dis[x]+cost[i]){dis[num[i]]=dis[x]+cost[i];if(!in[num[i]]){q.push((H){num[i]});in[num[i]]=true;}}}}return dis[t];
}int main()
{cin >> n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) id[i][j]=++cnt;s=++cnt;t=++cnt;for(int i=1;i<=n;i++) id[0][i]=s,id[n+1][i]=t,id[i][0]=t,id[i][n+1]=s;for(int x,i=0;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&x),add(id[i][j],id[i+1][j],x);for(int x,i=1;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&x),add(id[i][j+1],id[i][j],x);for(int x,i=0;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&x),add(id[i+1][j],id[i][j],x);for(int x,i=1;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&x),add(id[i][j],id[i][j+1],x);cout << SPFA() << endl;return 0;
}

这篇关于NOI2010 海拔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---