Diamond咋都是模板题。。。
开个坑刷codevs的Master题。巩固一下姿势。
目前AC的题目:1001,1021,1022,
1001.舒适的路线(并查集)
求出无向图s到t路径上的min(最大边权/最小边权).(n<=500,m<=5000)
边权排序一下，枚举最小边，将比它大的边权依次加入并查集直到s和t联通，此时的最大边权一定最小。复杂度O(m^2).
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
# define set pabs
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
, flag=;
char ch;
;
';
+(ch-');
return flag?-res:res;
}
void Out(int a) {
) {putchar('-'); a=-a;}
) Out(a/);
putchar(a%+');
}
;
//Code begin...
typedef struct{int u, v, w;}Node;
Node edge[];
int fa[N];
bool comp(Node a, Node b){return a.w<b.w;}
int find(int x)
{
int s, temp;
; s=fa[s]) ;
while (s!=x) temp=fa[x], fa[x]=s, x=temp;
return s;
}
void union_set(int x, int y)
{
int temp=fa[x]+fa[y];
if (fa[x]>fa[y]) fa[x]=y, fa[y]=temp;
else fa[y]=x, fa[x]=temp;
}
int gcd(int x, int y){return y?gcd(y,x%y):x;}
int main ()
{
];
double answer=INF;
scanf("%d%d",&n,&m);
FOR(i,,m) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
scanf("%d%d",&s,&t);
sort(edge+,edge+m+,comp);
FOR(i,,m) {
mem(fa,-);
mi=edge[i].w; ma=;
FOR(j,i,m) {
u=edge[j].u, v=edge[j].v;
if (find(u)!=find(v)) union_set(find(u),find(v));
if (find(s)==find(t)) {ma=edge[j].w; break;}
}
]=ma/gcd(ma,mi), ans[]=mi/gcd(ma,mi);
}
if (fabs(answer-INF)<eps) puts("IMPOSSIBLE");
else {
]==) printf(]);
],ans[]);
}
;
}
1021.玛丽卡(最短路)
求出图中删一条边后产生的最短路的最大值。(n<=1000)
考虑图中的任何一条最短路，若删除除了这条最短路的其他边，则并无什么卵用，于是我们枚举删除这条最短路的边，更新答案即可。复杂度O(n*m*logm).
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
# define set pabs
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
, flag=;
char ch;
;
';
+(ch-');
return flag?-res:res;
}
void Out(int a) {
) {putchar('-'); a=-a;}
) Out(a/);
putchar(a%+');
}
;
//Code begin...
struct Edge{int p, next, w, flag;}edge[N*N];
struct qnode{
int v, c;
qnode(, ):v(_v),c(_c){}
bool operator <(const qnode &r)const{return c>r.c;}
};
, dis[N], pre[N], bian[N];
bool vis[N];
void add_edge(int u, int v, int w)
{
edge[cnt].p=v; edge[cnt].next=head[u]; edge[cnt].w=w;
edge[cnt].flag=; head[u]=cnt++;
}
void dij(int n, int start, int flag)
{
mem(vis,);
FOR(i,,n) dis[i]=INF;
priority_queue<qnode>que;
while (!que.empty()) que.pop();
dis[start]=; que.push(qnode(start,));
qnode temp;
while (!que.empty()) {
temp=que.top(); que.pop();
int u=temp.v;
if (u==n) break;
if (vis[u]) continue;
vis[u]=true;
for (int i=head[u]; i; i=edge[i].next) {
) continue;
int v=edge[i].p;
int cost=edge[i].w;
if (!vis[v]&&dis[v]>dis[u]+cost) {
dis[v]=dis[u]+cost;
que.push(qnode(v,dis[v]));
if (flag) pre[v]=u, bian[v]=i;
}
}
}
}
int main ()
{
int n, m, u, v, w;
scanf("%d%d",&n,&m);
while (m--) scanf("%d%d%d",&u,&v,&w), add_edge(u,v,w), add_edge(v,u,w);
dij(n,,);
int ans=dis[n];
; i=pre[i]) {
edge[bian[i]].flag=edge[bian[i]^].flag=;
dij(n,,);
ans=max(ans,dis[n]);
edge[bian[i]].flag=edge[bian[i]^].flag=;
}
printf("%d\n",ans);
;
}
1022.覆盖(二分图染色)
求在矩阵中1*2的格子最多能用多少。(n,m<=100)
显然矩阵的格子形成了一个二分图，类似奇偶校验，直接染色一遍，对于每个联通块取颜色的最小值加入答案。复杂度O(n*m).
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
, flag=;
char ch;
;
';
+(ch-');
return flag?-res:res;
}
void Out(int a) {
) {putchar('-'); a=-a;}
) Out(a/);
putchar(a%+');
}
;
//Code begin...
][]={,,-,,,,,-};
], n, m;
void dfs(int x, int y, int flag)
{
vis[x][y]=flag; se[flag]++;
FO(i,,) {
], py=y+ps[i][];
||px>n||py<||py>m||g[px][py]==||vis[px][py]) continue;
dfs(px,py,-flag);
}
}
int main ()
{
;
scanf("%d%d%d",&n,&m,&k);
;
FOR(i,,n) FOR(j,,m) g[i][j]^=;
FOR(i,,n) FOR(j,,m) &&vis[i][j]==) se[]=se[]=, dfs(i,j,), ans+=min(se[],se[]);
printf("%d\n",ans);
;
}