vsooda的专栏

打星号的表示个人认为比较经典，或是算法，构图比较好的题目1062* 昂贵的聘礼 枚举等级限制+dijkstra1087* A Plug for UNIX 2分匹配1094 Sorting It All Out floyd 或 拓扑1112* Team Them Up! 2分图染色+DP1125 Stockbroker Grapevine FLOYD1135

乱搞题，n-1减去起点，把剩下的点分成尽可能相等的两部分1、2（为了得到尽可能大的答案）对于1内部来讲，显然总能保证“新鲜”，在新鲜1后，不难看出2的每个点都对应着一个“新鲜”#include using namespace std;int main(){ int n; while(scanf("%d",&n),n) printf("%d\n",(n-1)>>1); ret

类似上题。#include #include #define inf 0x7fffffffstruct{ int v, pow, next;}edge[52*52*4];int n = 0, map[52][52], head[52*52], dis[52*52], dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};__int64 c

求两点之间的最短距离//memset(map, 0x1ffffff, sizeof(map));//错误的初始化方式正确使用memset的方式是，初始指定的是8位的数值。比如说memset(map, 0x3f, sizeof(map)); 则map如果是int类型，则被初始化为4个3f 即 0x3f3f3f3f#include using namespace std;#define

水。。#include using namespace std;const int N = 105;const int INF = 0x1fffffff;int map[N][N];int D[N];int flag[N];int n, m;void init(){ for(int i = 0; i < N; i++) for(int j = 0; j < N; j++

#include#include#includeusing namespace std;const long long INF = 1e18;const int VN = 105;int n;int m;long long d[VN][VN];long long X[VN];long long L1,L2,L3,L4;long long C1,C2,C3,C4;i

有重边，wa了半天。#include using namespace std;#define N 205int n, m;int map[N][N];int sea[N];int D[N];int flag[N];void floyd(){ for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k

分别用dijkstra 和floyd做了。。奇怪的是，时间都是15MS#include using namespace std;#define N 12int n, m;int map[N][N];int sea[N];int D[N];int flag[N];void floyd(){ for(int i = 0; i < n; i++) for(int j = 0;

注意记录后缀的方法。。#include #include int a[50][50];int c[50][50];int b[50];int find(int beg,int end){ while(c[beg][end]!=end) { printf("-->%d",c[beg][end]); beg=c[beg][end]; } printf("-->%d\n"

一些图论、网络流入门题总结、汇总2008-09-03 11:43最短路问题此类问题类型不多，变形较少POJ 2449 Remmarguts' Date(中等)http://acm.pku.edu.cn/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：ht

#include#define MAX 99999int mp[1001][1001];int main(){ int i,j,k; int x,y,cost; int len,min; int T,S,D; int visit[1024]; while(scanf("%d%d%d",&T,&S,&D)!=EOF) { for(i=0;i<1001;i++) {

走AB这条路的前提是: B到home的最短路比A到home的最短路要短，求满足这个要求的office到home的路有多少条SPFA：参考http://sgeteternal.iteye.com/blog/1148891spfa比dijkstra极大程度减少不必要的松弛操作。故而比dij快。#include #include #include #include #include