1656: [Usaco2006 Jan] The Grove 树木 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 258  Solved: 168 [Submit][Status][Discuss] Description The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She's just sure there is a way to do it by going from her start location to successive locations by walking 继续阅读 >>


楚东方 17/10/13 01:11:20
题目链接 S向每个人连一条容量为1 费用为0 的边 , 每个人向职位连容量为1 费用为-point的边,每个职位根据模式向T连费用为0的边. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10000; const int MAXM = 100000; const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow,cost; } edge[MAXM]; int head[MAXN],tol; int pre[MAXN],dis[MAXN]; bool vis[MAXN]; int N;//节点总个数,节点编号从0~N-1 void init(int n) { N = n; tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int cap,i 继续阅读 >>


楚东方 17/10/12 11:37:48
题目链接 经典的2-SAT问题,每个位都执行一次,把所有不满足条件的条件加入 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 700 + 5;//节点个数 struct TwoSAT { int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], c; bool dfs(int x) { if (mark[x^1]) return false; if (mark[x]) return true; mark[x] = true; S[c++] = x; for (int i = 0; i < G[x].size(); i++) if (!dfs(G[x][i])) return false; return true; } void init(int 继续阅读 >>


楚东方 17/10/12 09:35:59
题目链接 根据题意推出 任意i和j至少有一个为true (i || j) 表示 , 同类应该一个true一个false 可以用 (i || j) && (!i || !j) 表示 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100000 + 5; struct TwoSAT { int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], c; bool dfs(int x) { if (mark[x^1]) return false; if (mark[x]) return true; mark[x] = true; S[c++] = x; for (int i = 0; i < G[x].size(); i++) if (!dfs(G[ 继续阅读 >>


楚东方 17/10/11 22:14:22
题目链接 把物品作为点,物品的交换通过与物品点的连线实现 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 继续阅读 >>


楚东方 17/10/11 21:43:21
题目链接 首先算出i在剩下比赛中全部获胜,看剩下的是否互相牵制,这样就转化成了公平分配问题的模型. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j 继续阅读 >>


楚东方 17/10/11 21:10:01
题目链接 问题分析 第一问时LIS,动态规划求解,第二问和第三问用网络最大流解决。 建模方法 首先动态规划求出F[i],表示以第i位为结尾的最长上升序列的长度,求出最长上升序列长度K。 1. 把序列每位i拆成两个点 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 100010 #define MAXM 10000000+10 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow, next; }; Edge edge[MAXM]; int head[MAXN], cur[MAXN], edgenum; int dist[MAXN]; bool vis[MAXN]; int N, M,ss,tt; void init() { edgenum = 0; memset(head, -1, sizeof(head)); } void 继续阅读 >>


楚东方 17/10/11 01:07:21
题目链接 要点,每个点之间可以连两条边,这样可以解决很多问题,该题中的数据被取出,则可以连一条有权重的边和若干条无权重的边. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10000; const int MAXM = 1000000; const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow,cost; } edge[MAXM]; int head[MAXN],tol; int pre[MAXN],dis[MAXN]; bool vis[MAXN]; int N;//节点总个数,节点编号从0~N-1 void init(int n) { N = n; tol = 0; 继续阅读 >>


楚东方 17/10/11 00:10:24
1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 761  Solved: 479 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 <= L <= 1,000,000 继续阅读 >>


楚东方 17/10/10 22:26:23
题目链接 建立二分图,跑一边最大流即可,最后再根据流量路径输出 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 41000; const int MAXM = 10000010; const int INF = 0x3f3f3f3f; //const ll MOD = 998244353; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48, rx=getchar();return ra*fh;} struct Edge { int fro 继续阅读 >>


楚东方 17/10/10 11:08:42