寒假日报2022.01.14

本文主要是介绍寒假日报2022.01.14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

早上听了2-sat的课程(就是解决离散的问题,转化位tarjan)
之后早上做了两道题一道模板题

//记得还需要判断以下这个是不是在栈当中
#include<cstdio>
#include<cstring>
#include<stack>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=2e6+50,M=2e6+50;
int h[N],e[M],ne[M],idx,ts,flag;
int vis[N];
stack<int>s;
int be[N],dfn[N],low[N];
void add(int u,int v)
{e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}
void tarjan(int u)
{low[u]=dfn[u]=++ts;s.push(u);vis[u]=1;for(int i=h[u];~i;i=ne[i]){int v=e[i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++flag;while(1){int v=s.top();s.pop();be[v]=flag;vis[v]=0;if(v==u){break;}}}
}
int main(){memset(h,-1,sizeof h);int n,m;scanf("%d%d",&n,&m);while(m--){int i,j,a,b;scanf("%d%d%d%d",&i,&a,&j,&b);add(2*i+!a,2*j+b);add(2*j+!b,2*i+a);}for(int i=2;i<2*n+2;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++)//编号的问题{if(be[2*i]==be[2*i+1]){puts("IMPOSSIBLE");return 0;}}puts("POSSIBLE");for(int i=1;i<=n;i++){if(be[2*i]<be[2*i+1]){printf("0 ");}else {printf("1 ");}}puts("");return 0;
}

//还有一道运用题,由于模板不熟悉,tarjan中的vis[v]=0弹出的时候忘记了从走上调道下午
//这个题的边我是用的异或来做

//自己去判断关系
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int N=1100*2,M=N*N;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],ts,be[N],vis[N],flag;
void add(int u,int v)
{e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}
struct node{int h,m,c;bool operator<(const node&a )const {if(h!=a.h)  return h<a.h;return m<=a.m;}node operator+(int x){int d=h;if(x>60){d+=x/60;x%=60;}if(m+x<60){return {d,m+x,c};}return {d+1,m+x-60,c};}node operator-(int x){int d=h;if(x>60){d-=x/60;x%=60;}        if(m>=x){return {d,m-x,c};}return {d-1,m-x+60,c};}
}t[M];
int n;
bool get(node a,node b)
{node d=a+a.c;node e=b+b.c;// cout<<a.h<<" "<<a.m<<" "<<a.c<<" "<<d.h<<" "<<d.m<<" "<<d.c<<endl;   // cout<<b.h<<" "<<b.m<<" "<<b.c<<" "<<e.h<<" "<<e.m<<" "<<e.c<<endl;   if(d<b){// cout<<1<<endl;return false;}if(e<a) {// cout<<2<<endl;return false;}// cout<<3<<endl;return true;
}
void build()
{for(int i=0;i<2*n;i++){for(int j=i+1;j<2*n;j++){if(get(t[i],t[j]))//两者之间存在矛盾的情况,存在一个交集{add(i,j^1);add(j,i^1);}}}
}
stack<int>s;
void tarjan(int u)
{dfn[u]=low[u]=++ts;s.push(u);vis[u]=1;for(int i=h[u];~i;i=ne[i]){int v=e[i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++flag;while(1){int v=s.top();s.pop();be[v]=flag;vis[v]=0;if(v==u){break;}}}
}
int main(){memset(h,-1,sizeof h);   scanf("%d",&n);int a,b,c,d,e;for(int i=0;i<n;i++){scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&e);t[i*2]=(node){a,b,e};t[i*2+1]=(node){c,d,e}-e;auto y=t[i*2+1];// cout<<y.h<<" "<<y.m<<" "<<y.c<<endl;}build();for(int i=0;i<2*n;i++){if(!dfn[i]){tarjan(i);}}for(int i=0;i<n;i++){if(be[i*2]==be[i*2+1]){cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;for(int i=0;i<n;i++){if(be[i*2]<be[i*2+1]){node x=t[i*2]+t[i*2].c;printf("%02d:%02d %02d:%02d\n",t[i*2].h,t[i*2].m,x.h,x.m);}else {node x=t[i*2+1]+t[i*2+1].c;printf("%02d:%02d %02d:%02d\n",t[i*2+1].h,t[i*2+1].m,x.h,x.m);}}return 0;
}

还有一道题先放着不太会
然后开始朱刘算法其实就是有向图的最小生成树不过代码还没AC,有点困了
调出来了昨晚太困了,时间戳忘记写了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
const int N=110;
const double inf=1e8;
bool st[N];
double d[N][N],b[N][N];
bool g[N][N];
pdd a[N];
int pre[N];
int n,m,id[N],cnt,ts;
int vis[N];
int dfn[N],low[N];
double get_dis(int i,int j)
{double dx=a[i].x-a[j].x;double dy=a[i].y-a[j].y;return sqrt(dx*dx+dy*dy);
}void dfs(int u)
{st[u]=true;for(int i=1;i<=n;i++){if(g[u][i]&&!st[i]){dfs(i);}}
}bool check()//开始直接进行一个判断
{memset(st,false,sizeof st);dfs(1);for(int i=1;i<=n;i++){if(!st[i])  return false;}return true;
}//直接做好了
stack<int>s;
void tarjan(int u)//这一个做法的话一的编号的话就一定是1
{low[u]=dfn[u]=++ts;s.push(u);vis[u]=1;int v=pre[u];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]) low[u]=min(low[u],dfn[v]);if(low[u]==dfn[u]){++cnt;while(1){int v=s.top();s.pop();id[v]=cnt;vis[v]=0;if(v==u){break;}}}
}double work()
{double res=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!g[i][j])    d[i][j]=inf;else d[i][j]=get_dis(i,j);}//枚举}//初始化while(true){for(int i=1;i<=n;i++){pre[i]=i;for(int j=1;j<=n;j++){if(d[j][i]<inf&&d[j][i]<d[pre[i]][i]){pre[i]=j;}}//找出来之后的话就行了啊}memset(vis,0,sizeof vis);memset(dfn,0,sizeof dfn);cnt=0,ts=0;for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}if(n==cnt)  {for(int i=2;i<=n;i++)//后面之后的话{if(d[pre[i]][i]<inf)//需要设置以下res+=d[pre[i]][i];}break;}//环上的需要全部加上去for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){b[i][j]=inf;}}for(int i=2;i<=n;i++){if(id[i]==id[pre[i]]){res+=d[pre[i]][i];}}//结束了之后的话就是处理了for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=id[i],y=id[j];if(x==y)    continue;//内部的话是没有边的if(d[i][j]<inf){if(id[pre[j]]==id[j])   {b[x][y]=min(b[x][y],d[i][j]-d[pre[j]][j]);                 }else {b[x][y]=min(b[x][y],d[i][j]);}                    }}}memcpy(d,b,sizeof d);n=cnt;//结束了        }return res;
}int main(){while(~scanf("%d%d",&n,&m)){memset(g,false,sizeof g);for(int i=1;i<=n;i++){scanf("%lf%lf",&a[i].x,&a[i].y);}int u,v;while(m--){scanf("%d%d",&u,&v);if(u!=v&&v!=1){g[u][v]=true;}}if(!check()) printf("poor snoopy\n");else printf("%.2f\n",work());}return 0;
}