国内知名网站建设,个人怎样做网站,php网站开发使用技术PDF下载,深圳网页制作培训Kruskal定义不同的优先级
P3623 [APIO2008] 免费道路 给定一个无向图#xff0c;其中一些边是0#xff0c;其他边为1 两个不同的点之间都应该一条且仅由一条边连接 并保持刚好K条0#xff0c;求是否有解决方案 n2e4,m1e5 Kruskal定义不同的优先级 思路#xff1a;…Kruskal定义不同的优先级
P3623 [APIO2008] 免费道路 给定一个无向图其中一些边是0其他边为1 两个不同的点之间都应该一条且仅由一条边连接 并保持刚好K条0求是否有解决方案 n2e4,m1e5 Kruskal定义不同的优先级 思路Kruskal先以1边优先,筛出必须要的0边 之后Kruskal先添加必须要的的0边,再以0边优先把0边添加至k后,再添1边最后还要检查图的连通性
#include iostream
#include cstdlib
#include cstdio
#include algorithm
using namespace std;
const int N 1e6 10;
int n, m, k, fa[N], tot, cnt;
struct edge {int u, v, w;
}e[N], ans[N];
bool cmp1(edge e1, edge e2) {return e1.w e2.w;
}
bool cmp2(edge e1, edge e2) {return e1.w e2.w;
}
int find(int x) {return x fa[x] ? x:fa[x] find(fa[x]);
}
void init() {cnt tot 0;for (int i 1; i n; i) fa[i] i;
}
void check() {int tmp find(1);for (int i 2; i n; i) {int f find(i);if (f ! tmp) {printf(no solution\n);exit(0);}tmp f;}
}
int main()
{cin n m k;for (int i 1; i m; i)cin e[i].u e[i].v e[i].w;init();sort(e 1, e m 1, cmp1); //从大到小(1边优先)for (int i 1; i m; i) {int x find(e[i].u);int y find(e[i].v);if (x y) continue;fa[x] y;if (e[i].w 0) {tot, e[i].w -1; //定为必须边下次的Kruskal此边为最高优先级}}if (tot k) { //(1边优先)0边k,0边优先时,0边依然kprintf(no solution\n);return 0;}check();init(); sort(e 1, e m 1, cmp2);for (int i 1; i m; i) {int f1 find(e[i].u), f2 find(e[i].v);if (f1 f2) continue;if (e[i].w 1 || tot k) {fa[f1] f2;if (e[i].w 1) {tot, e[i].w 0;}ans[cnt] e[i];}}if (tot k) {printf(no solution\n);return 0;}check();for (int i 1; i cnt; i) {printf(%d %d %d\n, ans[i].u, ans[i].v, ans[i].w);}return 0;
}
几何联通
P3958 [NOIP2017 提高组] 奶酪 给定一个它的高度为 h,它的长度和宽度我们可以认为是无限大的奶酪有n个空洞坐标为x,y,z 统一半径为r能否利用已有的空洞跑 到奶酪的上表面去 深度优先搜索,不需要回溯进入和出来判断只需看z-r,zr和0,h的比较 n1e3,h,r1e9
#includeiostream
#includealgorithm
#includestring.h
#includecstring
#includemath.h
using namespace std;
const int N 1e3 10;
int n;
double h, r;
int vis[N];
int ans;
struct cir {double x, y, z;bool operator (const cir c)const { //按从低到高return z c.z; }
}a[N];
double dist(double x1, double y1, double z1, double x2, double y2, double z2){return sqrt((x2 - x1) * (x2 - x1) (y2 - y1) * (y2 - y1) (z2 - z1) * (z2 - z1));
}
void dfs(int now) {if (ans) return;if (a[now].z r h) {ans 1;return;}vis[now] 1;for (int i 1; i n; i) {if (vis[i]) continue;if (dist(a[now].x, a[now].y, a[now].z, a[i].x, a[i].y, a[i].z) 2 * r) continue;dfs(i);}
}
void solve() {memset(vis, 0, sizeof(vis));ans 0;cin n h r;for (int i 1; i n; i) {cin a[i].x a[i].y a[i].z;}sort(a 1, a 1 n);for (int i 1; i n; i) {if (a[i].z- r 0) {dfs(i); //深搜}}if (!ans) {cout No \n;}else {cout Yes \n;}
}
int main()
{int t;cin t;while (t--) solve();
}
二维联通
P2498[SDOI2012] 拯救小云公主 给定一个row行line列大小的矩阵给定n个boss的位置,需要从左下角到达右上角 找一条路径使到距离boss的最短距离最远,输出最远距离 n3000 思路小数二分最远距离,boss点作为圆心, 参考奶酪 左边界或上边界通过这些洞和右边界或下边界联通时,问题无解
#includeiostream
#includecstring
#includemath.h
#includequeue
using namespace std;
int dis[3001][3001];
int x[3001], y[3001];
int getdis(int x1, int y1, int x2, int y2) {return pow(x1 - x2, 2) pow(y1 - y2, 2);
}
bool able(int d, double r) {return r * r * 4 d;
}
int row, line, n;
queueintq;
bool vis[3001];
bool bfs(double r) {memset(vis, 0, sizeof(vis));while (!q.empty())q.pop();for (int i 1; i n; i) {if (row - y[i] r||x[i]r) { // 左下角(row, 0)出发通过这些圆q.push(i), vis[i] 1;}}while (!q.empty()) {int p q.front();q.pop();if (y[p] r|| line - x[p] r) { //右上角(0,line)通过这些圆return 0;}for (int i 1; i n; i)if (!vis[i] able(dis[p][i], r)) { vis[i] 1, q.push(i);}}return 1;
}
int main() {cin n line row;line--; row--;for (int i 1; i n; i) {cin x[i] y[i];x[i]--;y[i]--;}for (int i 1; i n; i)for (int j 1; j i; j)dis[i][j] dis[j][i] getdis(x[i], y[i], x[j], y[j]);double l 0, r min(row, line), mid;for (int i 1; i 60; i) {mid (l r) / 2;if (bfs(mid))l mid;else r mid;}printf(%.2lf\n, l);return 0;
}
视为T在S之间滑动转换为拓扑图目标所有窗口匹配即度数为0 (atcoder 329 E)
给定一个长度为n字符串S,长度为m的字符串T
将长度为n字符串全是#变成S操作用T替换S的部分区间
n2e5,m5
思路视为T在S之间滑动于是有n-m1的窗口
转换为拓扑图入度为每个窗口不匹配的数量一旦为0完全匹配边为该窗口不匹配的字符编号为(窗口编号i相连字符编号ij)
之后拓扑ans倒序后得到操作的顺序目标为所有窗口完全匹配因为视为T在S之间滑动
#includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestack#includeunordered_map#includeunordered_set#includebitset#includearrayusing namespace std;#define endl \n#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define int long long#define int128 __int128_t#define ll long long#define ld long doubletypedef unsigned long long ull ;#define fr(i,l,r) for(int il;ir;i)#define fer(i,x) for(int ie.head[x];i;ie.next[i])#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondtypedef pairint,int pr;const int N 1e610;const int mod998244353,inf1e18;int n,m;int a[N];mapint,intmp;void solve(){cinnm;string s,t;cinst;vectorintin(n1,m);vectorvectorinte(n1); //边 queueintq;for(int i0;in-m1;i){for(int j0;jm;j){if(s[ij]t[j]){in[i]--;if(in[i]0){ //完全与t对应q.push(i);}}else{e[ij].push_back(i); }}}vectorintans;while(!q.empty()){int uq.front();q.pop();ans.push_back(u);for(int i0;im;i){if(mp[ui]){continue;}mp[ui]1;for(auto it:e[ui]){in[it]--;if(in[it]0){q.push(it);}}}}reverse(ans.begin(),ans.end()); //每一次操作位置if(ans.size()n-m1){coutNo\n;}else{coutYes\n;}}signed main(){ios;int t1;// cint;while(t--) solve();return 0;}
