一本通刷题
一本通
图论part
1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1346
并查集，初始化，路径压缩，合并
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e5+52;
int f[N];
int n,m;
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
rep(i,1,n+1) f[i]=i;
while(m--)
{
int a,b;a=read(),b=read();
int ax=find(a),bx=find(b);
if(ax!=bx) f[ax]=bx;
}
int q;
q=read();
while(q--)
{
int a,b;a=read(),b=read();
int ax=find(a),bx=find(b);
if(ax==bx) puts("Yes");
else puts("No");
}
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1385
扩展域并查集，通过数字union来表示关系。比如说a和b的反合并，同时b和a的反合并，对于相反的关系，通过对相反的反来合并，实现建立关系。
这里的集合是表示关系
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6;
int f[N];
int n,m;
bool vis[N];
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y)
{
int a=find(x),b=find(y);
if(a!=b) f[a]=b;
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
rep(i,1,2*n+1) f[i]=i;//扩展域并查集，通过集合来表示关系
while(m--)
{
int p,x,y;
p=read(),x=read(),y=read();
if(p==0) merge(x,y);//朋友直接合并
else merge(x,y+n),merge(x+n,y); //敌人和敌人的反合并
}
int cnt=0;
rep(i,1,n+1)
{
int tmp=find(i);//看有几个团伙
if(!vis[tmp])vis[tmp]=1,cnt++;
}
printf("%d\n",cnt);
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
计数的并查集在合并的时候处理一下就可以了
http://ybt.ssoier.cn:8088/problem_show.php?pid=1389
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6;
int f[N],cnt[N];
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int n,m;n=read(),m=read();
rep(i,1,n+1) f[i]=i,cnt[i]=1;
while(m--)
{
char ch[10];
scanf("%s",ch);
if(ch[0]=='M')
{
int a,b;a=read(),b=read();
int ax=find(a),bx=find(b);
if(ax!=bx) f[ax]=bx,cnt[bx]+=cnt[ax];
}
else if(ch[0]=='Q')
{
int a;a=read();
printf("%d\n",cnt[find(a)]);
}
}
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1388
换了个类型的并查集
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
map f;
string find(string x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
string st;
string tmp1,tmp2,tmp3;
while(cin>>st&&st!="$")
{
if(st[0]=='#')
{
tmp1=st.substr(1,st.size()-1);
if(f[tmp1]=="") f[tmp1]=tmp1;
}
else if(st[0]=='+')
{
tmp2=st.substr(1,st.size()-1);
find(tmp1);
f[tmp2]=f[tmp1];
}
else if(st[0]=='?')
{
tmp3=st.substr(1,st.size()-1);
find(tmp3);
cout< http://ybt.ssoier.cn:8088/problem_show.php?pid=1383
图的连通性问题，用并查集，头是自己的有几个，就知道有几个连通块了。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e4;
int f[N];
int g[N][N];
int n,x;
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
rep(i,1,n+1) while(x=read(),x) g[i][x]=1;
rep(i,1,n+1) rep(k,1,n+1) rep(j,1,n+1) if(g[i][k]&&g[k][j]) g[i][j]=1;
rep(i,1,n+1 ) f[i]=i;
rep(i,1,n+1) rep(j,1,n+1) if(g[i][j]) f[j]=f[i];//并查集求连通块，只要找头就可以了
int cnt=0;
rep(i,1,n+1) {
if(f[i]==i) cnt++;
// cout< http://ybt.ssoier.cn:8088/problem_show.php?pid=1384
求连通的数目的问题，只要连通块大于一半。floyd
每一个能到达的计数，每一个能出发的计数，分别代表了重过一半，和轻过一半
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n,m;
int g[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
while(m--)
{
int x,y;x=read(),y=read();
g[x][y]=1;
}
int cnt=0;
rep(i,1,n+1)
rep(k,1,n+1)
rep(j,1,n+1)
if(g[k][i]&&g[i][j])
g[k][j]=1;
rep(i,1,n+1 )
rep(j,1,n+1 )
g[0][j]+=g[i][j],g[i][0]+=g[i][j];//计数
rep(i,1,n+1)
if(g[0][i]>n/2||g[i][0]>n/2)
cnt++;
printf("%d\n",cnt);
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1381
很长时间没打了，dijkstra忘了，首先是加边，一定要初始化h，然后一开始的st不要，其次是取出来就要丢掉
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e5+520;
int e[N],w[N],ne[N],h[N],idx;
int n,m;
int dist[N];
bool st[N];
void add_edge(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
priority_queue,greater >heap;
heap.push({0,1});
while(heap.size())
{
auto t=heap.top();heap.pop();
int ver=t.y,dis=t.x;
if(st[ver]) continue;
st[ver]=true;
rept(i,ver)
{
int j=e[i];
if(dist[j]>dis+w[i]) dist[j]=dis+w[i],heap.push({dist[j],j});
}
}
if(dist[n]>INF/2) return -1;
else return dist[n];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
memset(h,-1,sizeof(h));
while(m--)
{
int a,b,c;a=read(),b=read(),c=read();
add_edge(a,b,c),add_edge(b,a,c);
}
printf("%d\n",dijkstra());
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1382
spfa，是每次拿更新过的去更新相连的人，一个人可能不止入队一次。又没有更新，又没有初始化h，同时还忘了更新dist。只有在dist更新之后且不在队才会入队，这里双向边也可以做。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6+52;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int q[N],dist[N];
bool st[N];
void add_edge(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int spfa(int start)
{
memset(dist,0x3f,sizeof(dist));
dist[start]=0;
int hh=0,tt=1;
q[0]=start,st[start]=true;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
rept(i,t)
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
q[tt++]=j;
if(tt==N) tt=0;
st[j]=true;
}
}
}
}
return dist[n];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
memset(h,-1,sizeof(h));
while(m--)
{
int a,b,c;a=read(),b=read(),c=read();
add_edge(a,b,c);add_edge(b,a,c);
}
printf("%d\n",spfa(1));
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1342
dijkstra double类型，首先就是定义类型不要错了，其次就是不要重名，不然很烦，再其次double 里面控制精度。
一个经验就是如果不可能的TLE发生了，有可能是数组开小了。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
typedef pair PDI;
const int N=5200;
bool st[N];
PII p[N*N];
int h[N],e[N],ne[N],idx;
double w[N];
double dist[N];
int s,ed,n,m;
double d(int a,int b)
{
return sqrt((double)(p[a].x-p[b].x)*(p[a].x-p[b].x)+(double)(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
void add_edge(int a,int b,double c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
double dijkstra(int s)
{
rep(i,1,n+1) dist[i]=1e9;
dist[s]=0;
priority_queue,greater > heap;
heap.push({0,s});
while(heap.size())
{
auto t=heap.top();heap.pop();
int ver=t.y;
double dis=t.x;
if(st[ver]) continue;
st[ver]=true;
rept(i,ver)
{
int j=e[i];
double eps2=1e-5;
if(dist[j]-dis-w[i]>eps2) dist[j]=dis+w[i],heap.push({dist[j],j});
} //标记出队
}
if(dist[ed]>INF/2) return -1;
else return dist[ed];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
memset(h,-1,sizeof(h));
rep(i,1,n+1)
{
int x,y;scanf("%d%d",&x,&y);
p[i]={x,y};
}
m=read();
while(m--)
{
int x,y;x=read(),y=read();
double di=d(x,y);
add_edge(x,y,di),add_edge(y,x,di);
}
s=read(),ed=read();
printf("%.2lf\n",dijkstra(s));
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
10
http://ybt.ssoier.cn:8088/problem_show.php?pid=1380
dijk，最长路，然后再加m
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=3e6;
int h[N],e[N],ne[N],idx;
int dist[N];
bool st[N];
int n,m,p,c;
void add_edge(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int s)
{
memset(dist,-0x3f,sizeof(dist));
priority_queue,greater > heap;
dist[s]=0;heap.push({0,s});
while(heap.size())
{
auto t=heap.top();heap.pop();
int ver=t.y,dis=t.x;
if(st[ver]) continue;
st[ver]=true;
rept(i,ver)
{
int j=e[i];
if(dist[j] in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),p=read(),c=read();
m=read();
memset(h,-1,sizeof(h));
while(p--)
{
int a,b;a=read(),b=read();
add_edge(a,b),add_edge(b,a);
}
dijkstra(c);
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
11
http://ybt.ssoier.cn:8088/problem_show.php?pid=1378
floyd，然后直接输出
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e4;
int a[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int b;
if(scanf("%d",&b)==1)//如果b是整数
a[i][j]=b;
else
a[i][j]=INF;
}
}//初始化
for(int k=1;k<=n;k++)//floyd
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
for(int i=1;i<=n;i++)
if(i!=s)
printf("(%d -> %d) = %d\n",s,i,a[s][i]);
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1395
一一配对问题，首先先把所有的输入解决，记录相互关系，已经可匹配个数。
做n次，然后每次对于每一个幻灯片，只找唯一对应的那个，因为一个点可能对应多个幻灯片，一个幻灯片也可能对应多个点，但是对于只有一个的而言，只要有一个对应即可。然后找到master，后面对所有和这个点，相连的去掉。（拓扑排序）
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=52;
int n;
int a[N],b[N],c[N],d[N];
int g[N][N];
int master[N];
int match[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
rep(i,1,n+1) a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
rep(i,1,n+1)
{
int x,y;x=read(),y=read();
rep(j,1,n+1)
{
if(x>=a[j]&&x<=b[j]&&y>=c[j]&&y<=d[j])
{
match[j]++;
g[i][j]=1;
}
}
}
int num=0,tmp;
rep(i,1,n+1)
{
rep(j,1,n+1)
{
if(match[j]==1)
{
num++;
match[j]--;
rep(k,1,n+1)
{
if(g[k][j])
{
g[k][j]=0,tmp=k,master[j]=k;break;
}
}
rep(k,1,n+1)
{
if(g[tmp][k])
{
g[tmp][k]=0;match[k]--;
}
}
}
}
}
if(num==n)
rep(i,1,n+1)
cout<<(char)(i-1+'A')<<" "< http://ybt.ssoier.cn:8088/problem_show.php?pid=1386
并查集的问题，反向建图，如果当前的合并无法满足要求，那么就直接删除。
反向验证是否成立
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1000+520;
int f[N];
int n;
vector a[N];
int sz[N];
int find(int x )
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
void merge(int a,int b)
{
f[b]=a;sz[a]+=sz[b];
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
rep(i,1,n+1)
{
int k;k=read();
rep(j,0,k)
{
int x;x=read();
a[i].push_back(x);
}
}
rep(i,1,n+1) f[i]=i,sz[i]=1;
int res=0;
per(i,n+1,1)
{
rep(j,0,a[i].size())
{
if(a[i][j]>i)//大于的才能加入反向构图
{
if(find(i)!=find(a[i][j])) merge(find(i),find(a[i][j]));
else continue ;
if(sz[i]>(n>>1)) {cout<