HDU 4360

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#define maxn 10000
#define maxe 200010
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int id;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn][4];
bool inque[maxn][4];
int num[maxn][4];
int n,m;
typedef struct node{
	int u;
	int id;
}node;
bool spfa(int s)
{
	int i,j;
	queue<node> q;
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		for(j=0;j<=3;j++)
		{
			dist[i][j]=inf;
			num[i][j]=0;
		}
	dist[s][3]=0;
	num[s][3]=0;
	node sr;
	sr.u=s;sr.id=3;
	q.push(sr);
	inque[s][3]=1;
	while(!q.empty())
	{
		int u=q.front().u;id=q.front().id;
		q.pop();
		inque[u][id]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int x=edge[i].id;
			if(dist[u][id]+edge[i].w<dist[v][x] && (id+1)%4==x)
			{
				dist[v][x]=dist[u][id]+edge[i].w;
				num[v][x]=num[u][id];
				if(x==3)
					num[v][x]++;
			}
			else if(dist[u][id]+edge[i].w==dist[v][x] && (id+1)%4==x && num[v][x]<=num[u][id])
			{
				num[v][x]=num[u][id];
				if(x==3)
					num[v][x]++;
			
			}
			
		}
	}
	return true;
}
int index[200];
int main()
{
    int i,j;
	int t;
	index['L']=0;
	index['O']=1;
	index['V']=2;
	index['E']=3;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		int cnt=0;
		scanf("%d %d",&n,&m);
		char c;
		int u,v;
		__int64 w;
		for(i=1;i<=n;i++)
		{
			scanf("%d %d %I64d %c",&u,&v,&w,&c);
			getchar();
			edge[cnt].id=love1;
			edge[cnt].w=w;
			edge[cnt].to=v;
			edge[cnt].next=head[u];
			head[u]=cnt++;

			edge[cnt].id=love1;
			edge[cnt].w=w;
			edge[cnt].to=u;
			edge[cnt].next=head[v];
			head[v]=cnt++;

			
		
		}
	}
	system("pause");
	return 0;
}

图论500题

=============================以下是最小生成树+并查集======================================
【HDU】
1213 How Many Tables 基础并查集★
1272 小希的迷宫 基础并查集★
1325&&poj1308 Is It A Tree? 基础并查集★
1856 More is better 基础并查集★
1102 Constructing Roads 基础最小生成树★
1232 畅通工程 基础并查集★
1233 还是畅通工程 基础最小生成树★
1863 畅通工程 基础最小生成树★
1875 畅通工程再续 基础最小生成树★
1879 继续畅通工程 基础最小生成树★
3371 Connect the Cities 简单最小生成树★
1301 Jungle Roads 基础最小生成树★
1162 Eddy’s picture 基础最小生成树★
1198 Farm Irrigation 基础最小生成树★
1598 find the most comfortable road 枚举+最小生成树★★
1811 Rank of Tetris 并查集+拓扑排序★★
3926 Hand in Hand 同构图★
3938 Portal 离线+并查集★★
2489 Minimal Ratio Tree dfs枚举组合情况+最小生成树★
4081 Qin Shi Huang’s National Road System 最小生成树+DFS★★
4126 Genghis Khan the Conqueror 枚举+最小生成树+DFS(难)★★★★

1829&&poj2492 A Bug’s Life 基础种类并查集★
1558 Segment set 计算几何+并查集★
3461 Code Lock 并查集(有点难想到)★★
3367 Pseudoforest 最大生成树★
2473 Junk-Mail Filter 并查集+设立虚父节点(马甲)★★
3172 Virtual Friends 带权并查集★
3635 Dragon Balls 带权并查集★
3047 Zjnu Stadium 带权并查集★
3038 How Many Answers Are Wrong 种类并查集★★
2818 Building Block 带权并查集★
3234 Exclusive-OR 异或并查集(难)★★★
2121 Ice_cream’s world II 最小树形图(要输出根有点恶心)★★
4009 Transfer water 最小树形图(模板题)★
3311 Dig The Wells 斯坦纳树(状压DP)(模板题)★★
4085 Peach Blossom Spring 斯坦纳树(状压DP)(有可能是森林…)★★★

2586 How far away ? LCA★
2874 Connections between cities LCA★
3486 Interviewe RMQ★
2888 Check Corners 二维RMQ★
3183 A Magic Lamp RMQ(有点难想到,有点难联系到RMQ)★★

【POJ】
1258 最经典的MST★
1789 Truck History 最小生成树★
1287 Networking 简单★
2349 Arctic Network 简单★
1611 The Suspects 并查集★
2377 kruskal★
2524 Ubiquitous Religions 并查集★
2236 Wireless Network 并查集+计算几何★
2560 Kruskal 并查集★
1861 Kruskal ★
3625 prim★
1679 – The Unique MST(基础) 判断MST是否唯一★
3522 – Slim Span(基础) 求一颗生成树,让最大边最小边差值最小★
2485 Highways MST中的最长边★
2395 最小生成树的最长边★
1751 Highways 求出方案★
POJ-1182 食物链 种类并查集★★
POJ 1456 Supermarket 贪心+区间合并★
POJ-1703 种类并查集★
POJ-1988 种类并查集★
POJ-1733 Parity game 种类并查集,先要离散化一下,不影响结果★
POJ-1417 True Liars(难) 并查集+DP 种类并查集★★
POJ-2912 Rochambeau(难) baidu的题,很不错…是食物链的加强版.判断裁判比较难想.★★★
POJ 2728 Desert King(中等) 最优比率生成树★★
POJ 1639 Picnic Planning(较难) 顶点度数有限制的最小生成树★★
POJ 3164 Command Network(难) 最小树形图★★

poj3723 好题!!! ★★
poj3228 好好题!!! ★★

【ZOJ】
ZOJ-3261 逆向并查集 ★★

===============================以下是最短路系列====================================
【HDU】
1548 A strange lift 基础最短路(或bfs)★
2544 最短路 基础最短路★
3790 最短路径问题 基础最短路★
2066 一个人的旅行 基础最短路(多源多汇,可以建立超级源点和终点)★
2112 HDU Today 基础最短路★
1874 畅通工程续 基础最短路★
1217 Arbitrage 货币交换 Floyd (或者 Bellman-Ford 判环)★
1245 Saving James Bond 计算几何+最短路★
1317 XYZZY Bellman-Ford判环,有负权★
1535 Invitation Cards 有向图的来回最短路,(反向建图)★
1546 Idiomatic Phrases Game 最短路★
2680 Choose the best route 最短路★
2923 Einbahnstrasse 最短路★
3339 In Action 最短路+背包★
2224 The shortest path 双调旅行商问题★★
2807 The Shortest Path 矩阵运算+最短路(floyd)★★
1595 find the longest of the shortest枚举+最短路(删掉任意一条边的最长最短路)★★
3986 Harry Potter and the Final Battle 枚举+最短路(删掉任意一条边的最长最短路)★★
1599 find the mincost route floyd求最小环★
1839 Delay Constrained… 二分下限+最短路(带限制最短路)★★
3631 Shortest Path Floyd插点法★★
4114 Disney’s FastPass 最短路+二维状压DP(难)★★★
3832 Earth Hour 三点连通(斯坦纳树)★
3873 Invade the Mars Dij变体(好题!,带限制最短路)★★★
4063 Aircraft 几何构图+最短路★★★★

hdu4179 Difficult Routes dis[][]开二维状态的最短路(带限制最短路)★★

1869 六度分离 Floyd最短路★
1385 Minimum Transport Cost 最短路+输出路径(输出字典序最小路径,有点恶心)★★
1224 free DIY Tour 最短路+输出路径★
1142 A Walk Through the Forest 最短路+记忆搜索★★
1596 find the safest road 乘积最小的最短路★
1598 find the most comfortable road 二分速度差+最短路(带限制最短路)★★
2722 Here We Go(relians) Again 最短路★
2962 Trucking 二分+最短路(带限制最短路)★★
1690 Bus System 最短路★
2433 Travel 删边+最短路之和(预处理桥边)★★★
2363 Cycling 二分+最短路(带限制最短路)★★
2377 Bus Pass 最短路(寻找一个点的最长最短路最小)★★
2833 WuKong 最短路+记忆化搜索(求两条最短路的最多公共点)★★
1688 Sightseeing 最短次短路条数★★
3191 How Many Paths Are There 次短路条数★★
2482 Transit search 最短路★★★
3768 Shopping 最短路+dfs(或最短路+状压DP)★★
3035 War 平面图最小割(建图麻烦)★★
3870 Catch the Theves 平面图最小割(建图麻烦)★★
3860 Circuit Board 平面图最小割(建图麻烦)★★

【POJ】
1062 昂贵的聘礼 竟然可以和最短路联系起来★★
1094 Sorting It All Out Floyd判环+拓扑排序★
1125 Stockbroker Grapevine Floyd★
1135 Domino Effect 最短路,比较有意思★★
1161 Walls 最短路(图太恶心了)★★
1502 MPI Maelstrom Floyd★
1511 Invitation Cards 来回最短路★
1556 The Doors 计算几何+最短路★★
1724 ROADS 带限制的最短路,dis[][]开二维来记录信息(或广搜)★★
1734 Sightseeing trip floyd最小环路径★
1797 Heavy Transportation 二分枚举+最短路★
1847 Tram 简单最短路★
1860 Currency Exchange 货币兑换★
1949 Chores 反向建边,求最长路★★
2139 Six Degrees of Cowvin Bacon Floyd★
2240 Arbitrage 货币兑换★
2253 Frogger 二分+最短路★
2312 坦克大战 spfa最短路本质变形–>广搜★
2387 Til the Cows Come Home 基础最短路★
2394 Checking an Alibi 最短路★
2449 Remmarguts’ Date A*求第K短路★★
2457 Part Acquisition 最短路 (输出路径)★★
2472 106 miles to Chicago 乘积最短路(log一下,乘变加)★★

2502 Subway
2570 Fiber Network floyd
3013 圣诞树
3037 Skiing
3072 Robot
3114 Countries in War 强联通+最短路
3160 Father Christmas flymouse 强联通+最长路
3255 Roadblock
3259 Wormholes (寻找负权回路)
3268 Silver Cow Part
3311 Hie with the Pie floyd+状压
3328 Cliff Climbing
3439 Server Relocation
3463 Sightseeing 次短路条数
3159
3521 Geometric Map 计算几何+最短路
3549 GSM phone 计算几何+最短路
3594 Escort of Dr. Who How
3613 Cow Relays 经过N条边的最短路 // floyd + 二分矩阵
3615 Cow Hurdles
3621 最优比率环
3635 full tank?
3660 传递闭包
3662 Telephone Lines
============================以下是差分约束系列============================
【HDU】
1384 Intervals
1529 Cashier Employment
1531 King
1534 Schedule Problem
3440 House Man
3592 World Exhibition
3666 THE MATRIX PROBLEM

【POJ】
1201
1275
1364
1716
2949
2983
3159
3169
3687

============================以下是二分匹配系列============================
普通匹配,多重匹配

【HDU】

1068 Girls and Boys
1150 Machine Schedule
1151 Air Raid
1179 Ollivanders: Makers of Fine Wands since 382 BC.
1281 棋盘游戏
1498 50 years, 50 colors
1507 Uncle Tom’s Inherited Land*
1528 Card Game Cheater
1845 Jimmy’s Assignment
2063 过山车
2119 Matrix
2444 The Accomodation of Students
2768 Cat vs. Dog
3081 Marriage Match II
3360 National Treasures
1045 也可搜索
1350 最小路径覆盖
3118 类似二分匹配
3729
2389
1054
2819 完全匹配
1668 二分+多重匹配
3605 多重匹配
3861 强连通+二分匹配
2236 无题II

hdu3468
hdu4185 奇偶匹配

【POJ】
1087 A Plug for UNIX
1274 The Perfect Stall
1469 COURSES
1486 Sorting Slides 二分图的必须边
1548 Robots
1698 Alice’s Chance
1719 Shooting Contest
1904 King’s Quest 求二分图所有可能的匹配边
2060 Taxi Cab Scheme 最小路径覆盖
2112 Optimal Milking 二分+多重匹配
2226 Muddy Fields 行列的覆盖
2239 Selecting Courses
2289 Jamie’s Contact Groups 二分+多重匹配
2446 Chessboard
2536 Gopher II
2584 T-Shirt Gumbo
2594 Treasure Exploration 可相交最小路径覆盖
2672 Hotkeys
2724 Purifying Machine
3020 Antenna Placement
3041 Asteroids 简单行列匹配
3189 Steady Cow Assignment 二分+多重匹配
3207 Ikki’s Story IV – Panda’s Trick
3216 Repairing Company
3343 Against Mammoths
3692 Kindergarten
2771 最大独立集
============================以下是KM算法系列============================
【HDU】
2255 奔小康赚大钱
1533 Going Home
1853 Cyclic Tour
3488 Tour
3435 A new Graph Game
2426 Interesting Housing Problem
2853 Assignment
3718 Similarity
3722 Card Game
3395 Special Fish
2282 Chocolate
2813 One fihgt one
2448 Mining Station on the Sea
3315 My Brute
3523 Image copy detection

【POJ】
2195 Going Home 最小权值匹配
2400 Supervisor, Supervisee 输出所有最小权匹配
2516 Minimum Cost 最小权值匹配或最小费用流
3565 Ants
3686 The Windy’s 最小权值匹配

============================以下是最大团&稳定婚姻系列============================
【HDU】

1530 Maximum Clique
1435 Stable Match
3585 maximum shortest distance 二分+最大团
1522 Marriage is Stable
1914 The Stable Marriage Problem

【POJ】

1129 四色定理 着色问题
1419 最大独立集
2989 极大团
3487 The Stable Marriage Problem 稳定婚姻
============================以下是强双联通系列============================
【HDU】
强连通:
1269 迷宫城堡 判断是否是一个强连通
2767 Proving Equivalences 至少加几条边让整个图变成强连通
3836 Equivalent Sets 至少加几条边让整个图变成强连通
1827 Summer Holiday 传递的最小费用
3072 Intelligence System 传递的最小费用
3861 The King’s Problem 强连通+二分匹配
3639 Hawk-and-Chicken 强连通缩点 + 树形dp(累加子节点的总权值)
3594 Cactus 仙人掌图

双连通:
2242 考研路茫茫——空调教室 双联通缩点+树形DP
2460 Network 边双连通
3849 By Recognizing These Guys, We Find Social Networks Useful 双连通求桥
3896 Greatest TC 双连通
4005 The war 边双连通

LCA:
2586 How far away ?
2874 Connections between cities
3078 Network LCA+排序
3830 Checkers 二分+LCA

【POJ】
强连通:
1236 Network of Schools
2553 The Bottom of a Graph 好题! 找出度为0的集合
2186 Popular Cows 好题! 找出度为0的,其他分量都指向它的集合
2375 Cow Ski Area 强连通
2762 Going from u to v or from v to u? 缩点+拓扑排序
3160 Father Christmas flymouse 强连通+最短路
3180 The Cow Prom 判断有几个环, 分量中元素大于1的个数
3114 Countries in War 强连通+最短路
3592 Instantaneous Transference 强连通分量+最长路
1904 King’s Quest 强连通+并查集

双连通:
3694 Network 边双连通 (同hdu2460)
3177 Redundant Paths 构造边双连通
3352 Road Construction 构造边双连通
2942 Knights of the Round Table (点双连通经典题)
1515 Street Directions (无向图改有向图)
1438 One-way Traffic (混合图改有向图)

LCA:
1330 Nearest Common Ancestors
1470 Closest Common Ancestors
1986 Distance Queries
3417 Network
3728 The merchant LCA+并查集,更新询问
2763 Housewife Wind LCA+树状数组
============================以下是2-SAT系列============================
【HDU】
3062 Party
1824 Let’s go home
3622 Bomb Game
3715 Go Deeper
1815 Building roads
2723 Get Luffy Out
1816 Get Luffy Out *
1814 Peaceful Commission
4115 Eliminate the Conflict

【POJ】
2296 Map Labeler
2723 Get Luffy Out
2749 Building roads
3207 Ikki’s Story IV – Panda’s Trick
3648 Wedding
3678 Katu Puzzle
3683 Priest John’s Busiest Day
3905 Perfect Election
============================以下是欧拉回路系列============================
【HDU】
1878 欧拉回路 判断
3018 Ant Trip 一笔画问题
1116
2894 兹鼓欧拉回路
1956
3472 混合欧拉

【POJ】
2513 欧拉路
1041 John’s trip 欧拉回路
1386 Play on Words 单词接龙
2230 Watchcow 欧拉回路
2513 Colored Sticks 无向图欧拉路
2337 Catenyms 欧拉路径
1392 Ouroboros Snake 兹鼓欧拉回路
1780 code
1637 混合欧拉

【zoj】
1992
============================以下是拓扑排序系列============================
【HDU】
1285 确定比赛名次
2094 产生冠军
2647 Reward
3342 Legal or Not
1811 Rank of Tetris 拓扑+并查集
3231 三维拓扑

【POJ】
1094 Sorting It All Out Floyd+拓扑
2367 Genealogical tree
3660 Cow Contest
3687 Labeling Balls 神奇的拓扑
1128 Frame Stacking DFS版拓扑
1270 Following Orders 拓扑+回溯
1420 Spreadsheet 模拟拓扑
2762 Going from u to v or from v to u? 强连通+拓扑
3553 Task schedule
============================以下是竞赛图系列============================
竞赛图下的哈密顿问题

Strange Country II ZOJ-3332
Task Sequences POJ-1776
The book SGU-122
Tour Route POJ-3780
Tour Route HDOJ-3414
============================以下是网络流系列============================
【HDU】

1532 Drainage Ditches(基础) [最大流]
3549 Flow Problem(基础) [最大流]
3572 Task Schedule [最大流]任务分配,判断满流
2732 Leapin’ Lizards(难) [最大流]
3338 Kakuro Extension [最大流][数和]神奇最大流行进列出
2883 kebab [最大流]判断满流
3605 Escape [最大流](多重匹配
3081 Marriage Match II [二分最大流]+并查集
3277 Marriage Match III [二分最大流]同上,多了拆点
3416 Marriage Match IV [最大流]最短路+最大流
2485 Destroying the bus stations [最大流]最短路+最大流
3468 Treasure Hunting [最大流](二分匹配)+最短路
3551 Hard Problem [最大流]
3998 Sequence(难) [DP+最大流]最长上升子序列
3917 Road constructions [最大权闭包]
3879 Base Station [最大权闭包]
3061 Battle [最大权闭包]
3996 Gold Mine [最大权闭包]
3472 HS BDC [混合欧拉]
hdu4183 来回走不重复点的网络流.
————————-
1533 Going Home(基础) [费用流]
3488 Tour [费用流]圈
3435 A new Graph Game [费用流]圈
1853 Cyclic Tour [费用流]圈
2686 Matrix [费用流]
3376 Matrix Again [费用流]
3667 Transportation [费用流]拆边
3315 My Brute [费用流](可用KM)
3395 Special Fish [费用流](可用KM匹配)
2448 Mining Station on the Sea [费用流](可用最短路+KM匹配)
4067 Random Maze(难) [费用流]
3947 River Problem(难) [费用流]神奇费用流,流量不等式建图
3046 Pleasant sheep and big big wolf [最小割]
1565 方格取数(1) [最小割]
1569 方格取数(2) [最小割]
3820 Golden Eggs [最小割]方格加强
3491 Thieves [最小割]最小点割集
3657 Game [最小割]最大点权独立集
3313 Key Vertex [最小割]
3251 Being a Hero [最小割]
3157 Crazy Circuits [上下流]
3002 King of Destruction [全局最小割]
3691 Nubulsa Expo [全局最小割]
【POJ】
1087 A Plug for UNIX [最大流](可用二分匹配)
1274 The Perfect Stall [最大流](可用二分匹配)
1325 Machine Schedule [最大流](可用二分匹配)
1698 Alice’s Chance [最大流](可用二分匹配)
2239 Selecting Courses [最大流](可用二分匹配)
2446 Chessboard [最大流](可用二分匹配) 好题啊
2536 Gopher II [最大流](可用二分匹配)
2771 Guardian of Decency [最大流]二分匹配最大独立集
3041 Asteroids [最大流](简单二分匹配)
2584 T-Shirt Gumbo [最大流](多重匹配)
3189 Steady Cow Assignment(中等) [二分最大流](多重匹配)
1149 PIGS [最大流] 绝对经典的构图题
1273 Drainage Ditches [最大流](基础)
1459 Power Network(基础) [最大流]
3281 Dining [最大流]
2112 Optimal Milking(基础) [二分最大流]
2289 Jamie’s Contact Groups [二分最大流]
2391 Ombrophobic Bovines(中等) [二分最大流]
2455 Secret Milking Machine(基础) [二分最大流]
3228 Gold Transportation [二分最大流](并查集)
2699 The Maximum Number of Strong Kings(较难) [枚举人数 + 最大流]
3498 March of the Penguins(中等) [最大流]枚举汇点,满足点容量限制的网络流
2987 Firing(较难) [最大权闭包]
1637 Sightseeing tour(Crazy) [混合欧拉]
2135 Farm Tour [费用流] (来回最短路)
2175 Evacuation Plan(中等) [费用流] 消圈
2195 Going Home [费用流]
2516 Minimum Cost [费用流]
3422 Kaka’s Matrix Travels(中等) [费用流]拆点
3680 Intervals(较难) [费用流]经典,费用流+离散化
3686 The Windy’s [费用流](KM匹配)
3762 The Bonus Salary! [费用流]
1815 Friendship(中等) [最小割]最小点割集
1966 Cable TV Network(中等) [最小割]最小点割集
2125 Destroying The Graph(难) [最小割]最小点权覆盖
3084 Panic Room(中等,好题) [最小割]边连通度
3204 Ikki’s Story I – Road Reconstruction(基础) [最小割]求关键边
3308 Paratroopers(较难) [最小割]乘积取对数,最小点权覆盖
3436 ACM Computer Factory [最小割]收集流,残留搜集找边
3469 Dual Core CPU(中等) [最小割]收集流
3921 Destroying the bus stations [最小割]点连通
2396 Budget(中等) [有源汇的上下界可行流]
3155 Hard Life(很挑战一题) [最大密度子图]
2914 Minimum Cut [无向图最小割]
============================以下是dancing links系列============================
1001 Easy Finding POJ-3740
1002 Power Stations HDOJ-3663
1003 Treasure Map ZOJ-3209
1004 Lamp HDOJ-2828
1005 whosyourdaddy HDOJ-3498
1006 Bomberman – Just Search! HDOJ-3529
1007 Square Destroyer POJ-1084
1008 Matrix HDOJ-2119
1009 Divisibility HDOJ-3335
1010 Radar HDOJ-2295
1011 Fire station HDOJ-3656
1012 Repair Depots HDOJ-3156
1013 Dominoes HDOJ-2518
1014 Street Fighter HDOJ-3957
1015 Sudoku Killer HDOJ-1426
1016 Sudoku POJ-2676
1017 Sudoku POJ-3074
1018 Sudoku POJ-3076
1019 Su-Su-Sudoku HDOJ-2780
1020 Sudoku HDOJ-3111
1021 Sudoku HDOJ-3909
1022 Squiggly Sudoku HDOJ-4069
1023 Triangle War II ZOJ-3038
1024 A Puzzling Problem HDOJ-1603
1025 Maximum Clique HDOJ-1530
hust1017 精确覆盖。
fzu1686,nuaa1507 重复覆盖。
hit2199,2882,2959 精确覆盖(数独)。
SPOJ1771 精确覆盖(N皇后问题)。
poj3435

[/swource]

1003

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#define maxn 10010
#define maxe 20010
#define inf 1000000000
using namespace std;
typedef struct node{
	int point;
	double dist;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	double w;
	int from;
	int to;
	int next;
}Edge;
int head1[maxn],head2[maxn];
Edge edge1[maxe],edge2[maxe];
double dist1[maxn],dist2[maxn];
int pre[maxn];
bool visit[maxn];
int n,m;
typedef struct Point{
	int x,y,z;
}Point;
Point point[maxn];
int level[maxe];
void dij(int s,double* dist,Edge edge[],int head[])
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
double cal_dist(int u,int v)
{
	int x1=point[u].x,x2=point[v].x;
	int y1=point[u].y,y2=point[v].y;
	int z1=point[u].z,z2=point[v].z;
	double x=double(x1-x2);
	double y=double(y1-y2);
	double z=double(z1-z2);
	return sqrt(x*x+y*y+z*z);
}
double cal_planedist(int u,int v)
{
	int x1=point[u].x,y1=point[u].y;
	int x2=point[v].x,y2=point[v].y;
	double x=double(x1-x2);
	double y=double(y1-y2);
	return sqrt(x*x+y*y);

}
typedef struct Keyedge{
	int index;
	int u;
	int v;
}Keyedge;
Keyedge key[maxe];
int main()
{
    int i,j;
	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0)
	{
		int cnt1=0,cnt2=0;
		memset(head1,-1,sizeof(head1));
		memset(head2,-1,sizeof(head2));
		for(i=1;i<=n;i++)
		{
			scanf("%d %d %d",&point[i].x,&point[i].y,&point[i].z);
		}
		for(i=1;i<=m;i++)
		{
			int u,v;
			int index=2*(i-1);
			scanf("%d %d",&u,&v);
			double w=cal_dist(u,v);
			edge1[cnt1].w=w;
			edge1[cnt1].from=u;
			edge1[cnt1].to=v;
			edge1[cnt1].next=head1[u];
			head1[u]=cnt1++;

			edge1[cnt1].w=w;
			edge1[cnt1].from=v;
			edge1[cnt1].to=u;
			edge1[cnt1].next=head1[v];
			head1[v]=cnt1++;

			if(point[u].z>point[v].z)
			{
				level[index]=0;
				level[index+1]=(int)(100*(point[u].z-point[v].z)/cal_planedist(u,v));
			}
			else if(point[u].z<point[v].z)
			{
				level[index+1]=0;
				level[index]=(int)(100*(point[v].z-point[u].z)/cal_planedist(u,v));				

			}
			else
			{
				level[index]=level[index+1]=0;	
			}

			edge2[cnt2].w=w;
			edge2[cnt2].from=v;
			edge2[cnt2].to=u;
			edge2[cnt2].next=head2[v];
			head2[v]=cnt2++;

			edge2[cnt2].w=w;
			edge2[cnt2].from=u;
			edge2[cnt2].to=v;
			edge2[cnt2].next=head2[u];
			head2[u]=cnt2++;
		
		}
		int s,t,d;
		scanf("%d %d %d",&s,&t,&d);
		int cur=0;
		for(i=0;i<=cnt1-1;i++)
			if(level[i]==d)
			{
				key[++cur].index=i;
				key[cur].u=edge1[i].from;
				key[cur].v=edge1[i].to;

			}
			if(level[i]>d)
			{
				edge1[i].w=inf;
			}
		if(cur==0)
		{
			printf("None\n");
			continue;
		}
		dij(s,dist1,edge1,head1);
		cur=0;
		for(i=0;i<=cnt2-1;i++)
			if(level[i]>d)
			{
				edge2[i].w=inf;
			}

		dij(t,dist2,edge2,head2);
		double ans=inf;
		for(i=1;i<=cur;i++)
		{
			int u=key[i].u;
			int v=key[i].v;
			j=key[i].index;
			double tmp=dist1[u]+edge1[j].w+dist2[v];
			if(tmp<ans)
				ans=tmp;
		}
		printf("%.1lf\n",ans);



	
	
		scanf("%d %d",&n,&m);
	}

system("pause");
return 0;
}

hdoj2433

这题真的写的痛苦流涕,看代码长度就知道了,比赛时候遇到目测没几十分钟绝对无法写出来(想不想的到还是个问题。。)
不知道是不是oj的问题,同样的代码WA好几次,最后一次却过了。。
8184304 2013-04-27 13:14:48 Accepted 2433 1703MS 844K 2714 B C++ shadow
8183928 2013-04-27 11:23:12 Wrong Answer 2433 890MS 408K 2727 B C++ shadow
8183893 2013-04-27 11:17:05 Wrong Answer 2433 828MS 384K 2726 B G++ shadow
8183858 2013-04-27 11:10:06 Compilation Error 2433 0MS 0K 546 B C++ shadow
8183855 2013-04-27 11:09:51 Wrong Answer 2433 890MS 408K 2726 B C++ shadow
8182801 2013-04-26 23:53:22 Wrong Answer 2433 921MS 408K 2694 B C++ shadow
8182797 2013-04-26 23:52:49 Wrong Answer 2433 906MS 408K 2693 B C++ shadow
8182790 2013-04-26 23:51:54 Wrong Answer 2433 890MS 408K 2693 B C++ shadow
8181185 2013-04-26 21:12:40 Wrong Answer 2433 781MS 408K 2645 B C++ shadow
8181053 2013-04-26 21:01:47 Time Limit Exceeded 2433 2000MS 632K 2600 B C++ shadow
8181042 2013-04-26 21:00:55 Runtime Error
(ACCESS_VIOLATION) 2433 0MS 320K 2603 B C++ shadow

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define maxn 110
#define maxe 6010
#define inf 1000000000
using namespace std;
typedef struct Edge{
    int to;
    bool flag;
    int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int n,m;
int sr[maxn][maxe];
int counter[maxn];
int dist[maxn];
int sum[maxn];
bool visit[maxn];
queue<int> q;
int bfs(int p)
{
    int i;
    memset(visit,0,sizeof(visit));
    for(i=1;i<=n;i++)
        dist[i]=inf;
    q.push(p);
    visit[p]=1;
    dist[p]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!visit[v])
            {
                sr[p][++counter[p]]=i;
                sr[p][++counter[p]]=i^1;
                dist[v]=dist[u]+1;
                visit[v]=1;
                q.push(v);
                sum[p]+=dist[v];
            }
        }
    }
    for(i=1;i<=n;i++)
        if(dist[i]>=inf)
            return -1;
    return sum[p];
}
int bfs2(int p)
{
    int i;
    int sum=0;
    memset(visit,0,sizeof(visit));
    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[p]=0;
    visit[p]=1;
    q.push(p);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            if(edge[i].flag==1)
            {
                int v=edge[i].to;
                if(!visit[v])
                {
                    dist[v]=dist[u]+1;
                    sum+=dist[v];
                    visit[v]=1;
                    q.push(v);
                }
            }
        }
    }
    for(i=1;i<=n;i++)
        if(dist[i]>=inf)
            return -1;
    return sum;

}
int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int u,v;
        int cnt=0;
        memset(counter,0,sizeof(counter));
        memset(head,-1,sizeof(head));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&u,&v);
            edge[cnt].to=v;
            edge[cnt].flag=1;
            edge[cnt].next=head[u];
            head[u]=cnt++;

            edge[cnt].to=u;
            edge[cnt].flag=1;
            edge[cnt].next=head[v];
            head[v]=cnt++;
        }
        int sumall=0;
        bool flag=1;
        for(i=1;i<=n;i++)
        {
            int tmp=bfs(i);
            if(tmp==-1)
            {
                flag=0;
                break;
            }
            else
                sumall+=tmp;
        }
        if(!flag)
        {
            for(i=1;i<=m;i++)
                printf("INF\n");
            continue;
        }
        else
        {
            for(i=1;i<=n;i++)
                sort(sr[i]+1,sr[i]+1+counter[i]);
            for(i=1;i<=m;i++)
            {
                bool isinf=0;
                int ans=sumall;
                for(j=1;j<=n;j++)
                {
                    int index=2*(i-1);
                    if(binary_search(sr[j]+1,sr[j]+1+counter[j],index))
                    {

                        edge[index].flag=0;
                        edge[index+1].flag=0;
                        int result=bfs2(j);
                        edge[index].flag=1;
                        edge[index+1].flag=1;
                        if(result==-1)
                        {
                            isinf=1;
                            break;
                        }
                        ans=ans-sum[j]+result;
                    }

                }
                if(isinf==1)
                    printf("INF\n");
                else
                    printf("%d\n",ans);
            }
        }

    }

    return 0;
}

hdoj3768——最短路+dfs

因为要去的地方最多只有10个,所以从0出发先经过哪再经过哪可以dfs。当然要先进行s遍dij,求出要用到的点之间的最短路。设置数组d[15][15]。d[i][j]表示dest[i]到dest[j]的最短距离

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 100010
#define maxe 200010
#define inf 1000000000
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
int n,m;
int dest[15];
int ans,s;
bool visit[15];
int d[15][15];
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	bool visit[maxn];
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
void dfs(int pre,int cur,int len,int cnt)
{
	int i;
	if(cur!=0)
		visit[cur]=1;
	len+=d[pre][cur];
	if(cnt==s)
	{
		len+=d[cur][0];
		if(len<ans)
			ans=len;
		return;
	}
	for(i=1;i<=s;i++)
	{
		if(!visit[i])
		{
			dfs(cur,i,len,cnt+1);
			visit[i]=0;
		}
	
	}
	return;
}
int main()
{
    int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int cnt=0;
		memset(head,-1,sizeof(head));
		scanf("%d %d",&n,&m);
		n++;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			a++;
			b++;
			edge[cnt].w=w;
			edge[cnt].to=b;
			edge[cnt].next=head[a];
			head[a]=cnt++;

			edge[cnt].w=w;
			edge[cnt].to=a;
			edge[cnt].next=head[b];
			head[b]=cnt++;
		
		}
		scanf("%d",&s);
		for(i=1;i<=s;i++)
		{
			scanf("%d",&dest[i]);
			dest[i]++;
		}
		dest[0]=1;
		for(i=0;i<=s;i++)
		{
			dij(dest[i]);
			for(j=i;j<=s;j++)
			{
				if(i==j)
					d[i][j]=0;
				else
					d[i][j]=d[j][i]=dist[dest[j]];
			}
		}
		memset(visit,0,sizeof(visit));
		ans=inf;
		dfs(0,0,0,0);
		printf("%d\n",ans);
	
	
	
	
	
	}

//system("pause");
return 0;
}

1020

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 1000000000
int dest[15];
int dist[100000][100000];
int ans,s;
bool visit[15];
void dfs(int pre,int cur,int len,int cnt)
{
	int i;
	if(cur!=0)
		visit[cur]=1;
	len+=dist[pre][cur];
	if(cnt==s)
	{
		len+=dist[cur][0];
		if(len<ans)
			ans=len;
		return;
	}
	for(i=1;i<=s;i++)
	{
		if(!visit[dest[i]])
		{
			dfs(cur,dest[i],len,cnt+1);
			visit[dest[i]]=0;
		}
	
	}
	return;
}
int main()
{
    int t;
	int i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;

		scanf("%d %d",&n,&m);
		for(i=0;i<=n-1;i++)
			for(j=0;j<=n-1;j++)
				if(i==j)
					dist[i][j]=0;
				else
					dist[i][j]=inf;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&w);
			if(w<dist[a][b])
			{
				dist[a][b]=dist[b][a]=w;
			}
		}
		scanf("%d",&s);
		for(i=1;i<=s;i++)
		{
			scanf("%d",&dest[i]);
		}
		for(k=0;k<=n-1;k++)
			for(i=0;i<=n-1;i++)
				for(j=0;j<=n-1;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		memset(visit,0,sizeof(visit));
		ans=inf;
		dfs(0,0,0,0);
		printf("%d\n",ans);
	
	
	
	
	
	}

system("pause");
return 0;
}

hdoj3339——最短路+01背包

最短路+01背包,但还没完全想清楚。
在装入背包时是否有可能出现装入最优方案时impossible,但是选择一种次优方案却可以得到值?

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define maxe 10000000
#define inf 1000010
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
bool visit[maxn];
int n,m;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int dp[6000];
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int cnt=0;
		memset(head,-1,sizeof(head));
		scanf("%d %d",&n,&m);
		n++;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			a++;
			b++;
			edge[cnt].to=b;
			edge[cnt].w=w;
			edge[cnt].next=head[a];
			head[a]=cnt++;

			edge[cnt].to=a;
			edge[cnt].w=w;
			edge[cnt].next=head[b];
			head[b]=cnt++;
		}
		int pow[maxn];
		int V=0;
		for(i=1;i<=n-1;i++)
		{
			scanf("%d",&pow[i]);
			V+=pow[i];
		}
		dij(1);
		int len=0;
		for(i=2;i<=n;i++)
		{
			len+=dist[i];
			dist[i-1]=dist[i];
		}
		if(V&1)
			V/=2;
		else
			V=V/2-1;
		for(j=0;j<=V;j++)
			dp[j]=0;
		for(i=1;i<=n-1;i++)
			for(j=V;j>=0;j--)
			{
				if(j>=pow[i])
				{
					dp[j]=max(dp[j],dp[j-pow[i]]+dist[i]);
				
				}
			}
			int ans=len-dp[V];
			if(ans>=inf)
				printf("impossible\n");
			else
				printf("%d\n",ans);

		




		
	
	
	
	
	}

system("pause");
return 0;
}

hdoj2833——最短路加DP

这题思路网上而来。。但还是又不理解的地方。网上说可以一边dij,一边求出那些边在最短路中,不解中。。
dp[i][j]表示悟空到达i点,师傅到达j点时的最多公共点数.dp[i][j]=(i==j)+max{dp[i的前驱][j],dp[i][j的前驱]}
状态转移涉及的点都在最短路径上。(i都在悟空的最短路径上,j都在师傅的最短路径上)
*************************************************************
dist[i]+map[i][j]=dist[j]。若j在最短路上,那么i在最短路上。
如果点数很多,不能用邻接矩阵时,可以用邻接表存图做最短路,但是因为要记忆化dp,所以这个图要用反邻接表存一下,以方便dp转移。(普通的链式前向星中是无法知道一个点的前驱的)

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define inf 1000000000
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
int map[maxn][maxn];
int d1[maxn],d2[maxn];
bool visit[maxn];
int n,m;
int max(int a,int b)
{
	return a>b?a:b;
}
void dij(int s,int* dist)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=1;i<=n;i++)
		{
			int v=i;
			if(map[u][v]!=inf && !visit[v] && dist[v]>dist[u]+map[u][v])
			{
				dist[v]=dist[u]+map[u][v];
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int dp[maxn][maxn];
int DP(int a,int b)
{
	if(dp[a][b]!=-1)
		return dp[a][b];
	int i,j,v=0;
	for(i=1;i<=n;i++)
		if(i!=a && d1[i]+map[i][a]==d1[a])
			v=max(v,DP(i,b));
	for(i=1;i<=n;i++)
		if(i!=b && d2[i]+map[i][b]==d2[b])
			v=max(v,DP(a,i));
	if(a==b)
		v++;
	dp[a][b]=v;
	return dp[a][b];
}
int main()
{
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF && (n!=0 || m!=0))
	{
		memset(dp,-1,sizeof(dp));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(i==j)
					map[i][j]=0;
				else
					map[i][j]=inf;
			}
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			if(w<map[a][b])
				map[a][b]=map[b][a]=w;
		}
		int s1,e1,s2,e2;
		scanf("%d %d %d %d",&s1,&e1,&s2,&e2);
		dij(s1,d1);
		dij(s2,d2);
		if(s1!=s2)
			dp[s1][s2]=0;
		else
			dp[s1][s2]=1;
		int ans=DP(e1,e2);
		printf("%d\n",ans);



	
	}
return 0;
}


hdoj1598

明天好好理解一下这段代码。。写的一知半解。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define maxn 210
#define maxe 2010
#define inf 1000000000
using namespace std;
typedef struct Edge{
    int w;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int pre[maxn];
int outque[maxn];
bool inque[maxn];
int n,m;
bool spfa(int low,int high,int s,int t)
{
    int i;
    queue<int> q;
    memset(outque,0,sizeof(outque));
    memset(inque,0,sizeof(inque));
    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[s]=0;
    inque[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inque[u]=0;
        outque[u]++;
        if(outque[u]>n-1) return false;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            int w=edge[i].w;
            if(w<low || w>high)
                continue;
            if(dist[v]>dist[u]+edge[i].w)
            {
                dist[v]=dist[u]+edge[i].w;
                if(v==t)
                    return true;
                if(!inque[v])
                {
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
    return false;
}

int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        int a,b;
        int cnt=0;
        int max=-1;
        int w[maxe];
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&w[i]);
            if(max<w[i])
                max=w[i];
            edge[cnt].w=w[i];
            edge[cnt].to=b;
            edge[cnt].next=head[a];
            head[a]=cnt++;

            edge[cnt].w=w[i];
            edge[cnt].to=a;
            edge[cnt].next=head[b];
            head[b]=cnt++;
        }
        int query;
        sort(w+1,w+1+m);
        scanf("%d",&query);
        for(i=1;i<=query;i++)
        {
            int start,end;
            scanf("%d %d",&start,&end);
            if(!spfa(0,max,start,end))
            {
                printf("-1\n");
                continue;

            }

            int l=0,r=max+1,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                bool flag=0;
                for(j=1;w[j]<=max-mid;j++)
                {
                    if(spfa(w[j],w[j]+mid,start,end))
                    {
                        flag=1;
                        break;
                    }

                }
                if(flag)
                {
                    r=mid;
                }
                else
                    l=mid+1;
            }
            printf("%d\n",l);



        }


    }
return 0;
}

hdoj1688——最短路及次短路长度及路径数

图中边权均>=1 ,所以可以在dij的过程中求出最短路径数量和次短路径数量。
这段代码可以作为边权>=1的图求最短路和次短路长度及路径数量的模版
注意理清这个过程:在这个过程中,由于dij的定标技术,所以和普通的dij一样,距离源点最短距离小的点会先被定标。所以一个点的最短路肯定比次短路先永久确定(显然,一个点的最短路肯定短于次短路)。

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1010
#define maxe 10010
#define inf 10000000
using namespace std;
typedef struct node{
	int dist,point;
	int flag;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn][2],pre[maxn][2];
int cnt[maxn][2];
bool visit[maxn][2];
int n,m;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
	{
		dist[i][0]=dist[i][1]=inf;
		cnt[i][0]=cnt[i][1]=0;
	}
	dist[s][0]=0;
	cnt[s][0]=1;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;sr.flag=0;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point,flag=x.flag;
		if(visit[u][flag]) continue;
		visit[u][flag]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(!visit[v][0] && dist[u][flag]+w<dist[v][0])
			{
				if(dist[v][0]<dist[v][1])
				{
					dist[v][1]=dist[v][0];
					cnt[v][1]=cnt[v][0];
					dist[v][0]=dist[u][flag]+w;
					cnt[v][0]=cnt[u][flag];
					node tmp;
					tmp.dist=dist[v][0];tmp.flag=0;tmp.point=v;q.push(tmp);
					tmp.dist=dist[v][1];tmp.flag=1;tmp.point=v;q.push(tmp);
				}
				else//说明最短路未曾更新,是inf
				{
					dist[v][0]=dist[u][flag]+w;
					cnt[v][0]=cnt[u][flag];
					node tmp;
					tmp.dist=dist[v][0];tmp.flag=0;tmp.point=v;q.push(tmp);
				
				}
			}
			else if(!visit[v][0] && dist[u][flag]+w==dist[v][0])
				cnt[v][0]+=cnt[u][flag];
			else if(!visit[v][1] && dist[u][flag]+w<dist[v][1])
			{
				dist[v][1]=dist[u][flag]+w;
				cnt[v][1]=cnt[u][flag];
				node tmp;
				tmp.dist=dist[v][1];tmp.flag=1;tmp.point=v;q.push(tmp);
			}
			else if(!visit[v][1] && dist[u][flag]+w==dist[v][1])
				cnt[v][1]+=cnt[u][flag];
		}
	}
	return;
}
int main()
{
	int cas,i;
	scanf("%d",&cas);
	while(cas--)
	{
		memset(head,-1,sizeof(head));
		int count=0;
		scanf("%d %d",&n,&m);
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			edge[count].to=b;
			edge[count].w=w;
			edge[count].next=head[a];
			head[a]=count++;
		}
		int s,t;
		scanf("%d %d",&s,&t);
		dij(s);
		int ans=cnt[t][0];
		if(dist[t][1]==dist[t][0]+1)
			ans+=cnt[t][1];
		printf("%d\n",ans);


	}
system("pause");
return 0;
}

关于dij和spfa的同时求最短路条数的问题小结

记一下昨晚想了很久的问题,今天又问了下学长,应该不会有错了。结论:对于边权>=1的图,可以在dij的过程中求出最短路径数量,如果有重边,则要用邻接表。如果边权中有0则不行。而spfa则不能在其过程中求出最短路径数量。

更进一步的,dij可以加上一维,同时求出次短路及其路径数量。

其根本性原理在于dij的贪心过程导致松弛一个点的时候这个点必定已经永久定标,而一个点的最短路必定是由dist较小的点才可能松弛过来的。这样,可以放心的对当前未定标的点中dist最小的点永久定标,因为此时不可能存在从其他未定标的点松弛过来得到一条或更多最短路。而spfa则不同,它是动态的修标,点u更新了到v的最短路条数后,可能u还有一条经过很多点的最短路没有松弛到,这样对于点v,明显漏了路径数。如果像dij那样松弛的时候相等也更新(对spfa来说就是dist[v]==dist[u]+edge(u,v)时v入队),那么这样虽然可能在u的最短路全找到之后更新v,但是很明显此时对于v,重复计算了很多路径(cnt[v]本来就记录了u的最短路没找完全时的cnt[u],u的最短路找全后cnt[v]又加上了cnt[u],显然加多了,进一步的,之后可能还会重复计数(u点可能还会因为某个点而重复判作有更新而入队))。

简单的解释就是这样。希望以后回顾还能记得这些。。其实自己这次看最短路才算真正看懂,上面的思路也很简略,甚至没有写关键的几个点,但是很多东西往往只能意会,只有在自己大脑中才会清晰明了,写是写不出来的。说句实话,对于像dij、spfa这样的经典算法,不仔细推敲上两三天(指的是第2、3次看)是不会真的理解的(不理解的话就只能做做裸题了)。。至少对于我来说是这样。

与图论相关的国家集训队论文集合

徐静:《图论模型的建立与转化》
江鹏:《从一道题目的解法试谈网络流的构造与算法》
金恺:《浅谈网络流算法的应用》
孙方成:《偶图的算法及应用》
周文超:《树结构在程序设计中的运用》
刘才良:《平面图在信息学中的应用》
伍昱:《由对称性解2-SAT问题》
吴景岳:《最小生成树算法及其应用》
贝小辉:《浅析树的划分问题》
黄源河:《浅谈图论模型的建立与应用》
汪汀:《最小生成树问题的拓展》
肖天:《“分层图思想”及其在信息学竞赛中的应用》
栗师:《树的乐园——一些与树有关的题目》
任恺:《图论的基本思想及方法》
王俊:《浅析二分图匹配在信息学竞赛中的应用》
陈首元:《维护森林连通性——动态树》
冯威:《数与图的完美结合——浅析差分约束系统》
贾由:《由图论算法浅析算法优化》
余远铭:《最短路算法及其应用》
湖南 仇荣琦 欧拉回路性质与应用探究
湖南 袁昕颢 动态树及其应用
上海 王欣上 浅谈基于分层思想的网络流算法
//广东 陈启峰 Size Balanced Tree
湖南 郭华阳 RMQ与LCA问题
福建 胡伯涛 最小割模型在信息学竞赛中的应用
安徽 周 冬 生成树的计数及其应用
吕子鉷《浅谈最短径路问题中的分层思想》
漆子超 《分治算法在树的路径问题中的应用》
姜碧野 《SPFA算法的优化及应用》
附上99——09论文全集>点我下载

 

hdoj1599

这几天狂刷webdiy,做了很多题目却来不及发上来总结,不多很多都是以前知识点的复习,今天学了最小环。这个写一下重点。
floyd求最小环关键代码

for(k=1;k<=n;k++)
{
////////////////////////////////////////////////////////////////////////
	for(i=1;i<=k-1;i++)
		for(j=i+1;j<=k-1;j++)
			if(map[k][i]+dist[i][j]+map[j][k]<ans)
				ans=map[k][i]+dist[i][j]+map[j][k];
/////////////////////////////////////////////////////////////////////////
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(dist[i][k]+dist[k][j]<dist[i][j])
				dist[i][j]=dist[i][k]+dist[k][j];
		}
}

可见,与普通floyd的唯一不同点就是斜线包含部分。以下称这部分代码为*代码
map[k][i]+dist[i][j]+map[j][k]代码求的是以k为环中最大编号的环的长度,其中i与j是与k点直接相连的点(这里没有判断i、j是否直接与k相邻,但可以保证正确,因为不相邻的点之间距离为inf,加起来之后肯定不是最小环,对结果无影响)。
为什么*代码要放在在前面
当要执行*代码时最外层循环已经执行了k-1次,这表示对于图中任意两点i、j,已经在它们之间插入了1——k-1这些点(用1——k-1这些点松弛过),所以此时任意两点i、j之间的最短路只可能经过了1——k-1这些点,不会经过k点,这样就保证了map[k][i]-dist[i][j]-map[j][k]形成的是环,也就是说没有重复经过同一点。
为什么*代码中i、j两层循环中i、j的范围是比k小?
因为已经约定*代码找的是以k为环中编号最大点的环的长度,按我的理解,其实这两层循环也可以写成
for(i=1;i<=m;i++){for(j=1;j<=n;j++){;}}
但是这样会重复计算很多环,大大降低了时间效率。

如果允许来回的路上经过重复点,并且没有必须经过两个不同点的限制,求指定的一个源点到任意点再回到源点的最短距离,可以怎么做?

答:可以用两次dij搞定,两次都是求出源点到任意点的最短路,只是第二次对应的图是原图的边方向反一下。
很显然,边反一下之后求出s到t的最短路其实是从t到s的最短路径。

#include<stdio.h>
#include<stdlib.h>
#define inf 10000000
#define maxn 110
int dist[maxn][maxn];
int map[maxn][maxn];
int main()
{
	int n,m;
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
				{
					map[i][j]=dist[i][j]=0;
				}
				else
				{
					map[i][j]=dist[i][j]=inf;
				}
		int a,b,c;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			if(c<dist[a][b])
			{
				map[a][b]=map[b][a]=dist[a][b]=dist[b][a]=c;
			}
		}
		int ans=inf;
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=k-1;i++)
				for(j=i+1;j<=k-1;j++)
					if(map[k][i]+dist[i][j]+map[j][k]<ans)
						ans=map[k][i]+dist[i][j]+map[j][k];
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		}

		
		if(ans>=inf)
			printf("It's impossible.\n");
		else
			printf("%d\n",ans);
	
	
	
	}

//system("pause");
return 0;
}

spfa模板

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 10000
#define maxe 100000
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int pre[maxn];
int outque[maxn];
bool inque[maxn];
int n;
bool spfa(int s)
{
	int i;
	queue<int> q;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n-1) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				if(!inque[v])
				{
					q.push(v);
					inque[v]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
    memset(head,-1,sizeof(head));	



	system("pause");
	return 0;
}

堆优化的dij模板

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define maxe 10000000
#define inf 1000000000
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
bool visit[maxn];
int n;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int main()
{
    memset(head,-1,sieof(head)):

system("pause");
return 0;
}