BZOJ 4289: PA2012 Tax(最短路)
2018-06-17 21:10:06来源:未知 阅读 ()
Submit: 755 Solved: 240
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
Sample Output
HINT
Source
这题居然卡long long,也是没谁了
首先一个很显然的思路是暴力拆边
即把每个点每一条入边和每一条出边的两两看做一个点,权值为两边的较大值
但是这样很显然是$O(m^2)$,肯定会GG
所以我们考虑一种神仙操作。
对于一条无向边,我们把它看成两条有向边
然后我们这样构图
1.对于一个点,我们把它的出边从小到大排序
2.枚举每一条边,如果这条边连接着1或者N,那么我们从S连向这条边或者从这条边连向T,权值为该边的权值
3.从改边所对应的入边向该边连一条边,边权为它们的权值
4.枚举每一条出边,从权值较小的向权值较大的连权值为两边差值的边,从权值较大的向权值较小的连权值为0的边
可能这样说不是很清楚,借鉴一下这位大佬的图
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> #define Pair pair<long long,int> #define F first #define S second const int MAXN=2*1e6+10; using namespace std; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Edge { int u,v,w,nxt; }E[MAXN]; int headE[MAXN],numE=2; inline void add_edge(int x,int y,int z) { E[numE].u=x; E[numE].v=y; E[numE].w=z; E[numE].nxt=headE[x]; headE[x]=numE++; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN],num=2; inline void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int N,M,S,T; int temp[MAXN]; long long dis[MAXN]; bool vis[MAXN]; void Dijstra() { memset(dis,0xf,sizeof(dis));dis[S]=0; priority_queue<Pair>q; q.push(make_pair(0,S)); while(q.size()!=0) { while(vis[q.top().second]&&q.size()>0) q.pop(); long long p=q.top().second; vis[p]=1; for(int i=head[p];i!=-1;i=edge[i].nxt) if(dis[edge[i].v]>dis[p]+edge[i].w) dis[edge[i].v]=dis[p]+edge[i].w, q.push(make_pair(-dis[edge[i].v],edge[i].v)); } printf("%lld\n",dis[T]); } int comp(const int &a,const int &b) { return E[a].w<E[b].w; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(headE,-1,sizeof(headE)); memset(head,-1,sizeof(head)); N=read();M=read();S=1,T=2*(M+1); for(int i=1;i<=M;i++) { int x=read(),y=read(),z=read(); add_edge(x,y,z); add_edge(y,x,z); } for(int i=1;i<=N;i++) { int tempnum=0; for(int j=headE[i];j!=-1;j=E[j].nxt) temp[++tempnum]=j; sort(temp+1,temp+tempnum+1,comp); for(int j=1;j<=tempnum;j++) { int x=temp[j],y=temp[j+1]; if(E[x].u==1) AddEdge(S,x,E[x].w); if(E[x].v==N) AddEdge(x,T,E[x].w); AddEdge(x^1,x,E[x].w); if(j!=tempnum) AddEdge(x,y,E[y].w-E[x].w), AddEdge(y,x,0); } } Dijstra(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash