题目链接 先从终点BFS到起点,并记录下其到终点的距离,然后从起点BFS到终点,并优先选取边权值小的. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9+10; const int maxn = 100005; struct node { int to; int col; }; vector<node> mm[maxn]; int inque[maxn]; int d[maxn]; int vis[maxn]; int ans[maxn]; int n,m; node nt; struct poin { int x; int step; }; void bfs() { //init inque ans d memset(inque,0,sizeof(inque)); memset(d,0,sizeof(d)); poin cur, 继续阅读 >>


楚东方 17/10/18 15:48:10
Play on Words Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8780    Accepted Submission(s): 3015 Problem Description Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.  There is a large number of magnetic plates 继续阅读 >>


楚东方 17/10/17 23:23:18
1659: [Usaco2006 Mar]Lights Out 关灯 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 315  Solved: 81 [Submit][Status][Discuss] Description 奶牛们喜欢在黑暗中睡觉。每天晚上,他们的牲口棚有L(3<=L<=50)盏灯,他们想让亮着的灯尽可能的少。他们知道按钮开关的位置,但喜闻乐见的是他们并没有手指。你得到了一个长度为T(1<=T<=7)的插槽用以帮助奶牛们改变灯的状态。 Input 第一行,两个整数L和T。第二行给出一个长度为L的01串表示初始灯的状态,0表示灯是灭的,1表示灯是亮的。第三行给出一个长度为T的01串,表示你获得的插槽。 Output 第一行输出一个整数K,表示在满足亮着的灯最少的情况下,你要用插槽操作的次数。第二行到第K+1行,每行一个整数表示你的插槽使用的位置。 "K最小的解, 继续阅读 >>


楚东方 17/10/16 17:46:14
Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1894    Accepted Submission(s): 631 Problem Description There are N bombs needing exploding. Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode. If a un-lighting bomb is in or on the b 继续阅读 >>


楚东方 17/10/16 01:21:42
传递 Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1476    Accepted Submission(s): 672 Problem Description 我们称一个有向图G是传递的,当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 我们称图G是一个竞赛图,当且仅当它是一个有向图且它的基图是完全图。换句 话说,将完全图每条边定向将得到一个竞赛图。 下图展示的是一个有4个顶点的竞赛图。 现在,给你两个有向图P = (V,Ep)和Q = (V,Ee),满足: 1.   EP与Ee没有公共边; 2.  (V,Ep⋃Ee)是一个竞赛图。 你的任务是:判定是否P,Q同时为传递的。 &nb 继续阅读 >>


楚东方 17/10/16 00:12:15
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