上课qwq《S2-一些图论算法》
T1 匈牙利算法《AC提款机1.0》
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
using namespace std;
const int N=201;
int n,m,acow,h,G[N],cow[N],ans,a[N][N];
int mat(int x)
{
fup(i,1,m) { if(a[x][i]&&!G[i]) { G[i]=1; if(!cow[i]||mat(cow[i])) { cow[i]=x; return 1; } } }
return 0;
}
signed main(void)
{
scanf("%d%d",&n,&m);
fup(i,1,n) { scanf("%d",&acow); fup(j,1,acow) scanf("%d",&h),a[i][h]=1; }
fup(i,1,n) memset(G,0,sizeof G ),mat(i);
fup(i,1,m) if(cow[i]>0) ans++;
printf("%d",ans);
return 0;
}
T2 类似吧《AC提款机2.0》
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
using namespace std;
const int N=1e6+10;
int to[N],nxt[N],head[N],cnt;
int n,t;
void ins(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int times,vis[N],match[N];
int dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(vis[y]==times) continue;
vis[y]=times;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return 1;
}
}
return 0;
}
void init()
{
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(to,0,sizeof(to));
memset(match,0,sizeof(match));
cnt=0;
}
signed main()
{
cin>>t;
while(t--)
{
init();
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
if(x)
{
ins(i,j+n);
ins(j+n,i);
}
}
int ans=0;
for(int i=1;i<=n;i++) times++,ans+=dfs(i);
if(ans==n) puts("Yes");
else puts("No");
}
return 0;
}
T3
他们说直接照改T1Code就可以了
《AC提款机3.0》
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
using namespace std;
const int N=505;
int n,m,acow,h,G[N],cow[N],ans,a[N][N];
int mat(int x)
{
fup(i,1,n) { if(a[x][i]&&!G[i]) { G[i]=1; if(!cow[i]||mat(cow[i])) { cow[i]=x; return 1; } } }
return 0;
}
signed main(void)
{
scanf("%d%d",&n,&m);
int x,y;
fup(i,1,m) { cin>>x>>y, a[x][y]=1; }
fup(i,1,n) memset(G,0,sizeof G ),mat(i);
fup(i,1,n) if(cow[i]>0) ans++;
printf("%d",ans);
return 0;
}
T4
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205;
int head[N*N*2],to[N*N*8],nxt[N*N*8],cnt=1,n,ans,tot=0;
int vis[N*N*2],cp[N*N*2];
int fx[9]={0,-1,-2,1,2,-1,-2,1,2};
int fy[9]={0,-2,-1,-2,-1,2,1,2,1};
char s[N][N];
void add(int u,int v)
{
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt++;
}
bool dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
int v=to[i];
if(vis[v]) continue;
vis[v]=true;
if(!cp[v]||dfs(cp[v]))
{
cp[v]=x;
return true;
}
}
return false;
}
signed main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i]+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]=='1')
{
tot++;
continue;
}
for(int k=1;k<=8;k++)
{
int x=i+fx[k],y=j+fy[k];
if(s[x][y]=='1') continue;
if(x>=1&&x<=n&&y>=1&&y<=n&&(i+j)%2==0) add((i-1)*n+j,(x-1)*n+y+n*n);
}
}
}
for(int i=1;i<=n*n;i++)
{
memset(vis,0,sizeof vis );
int k=dfs(i);
ans+=k;
}
printf("%d\n",n*n-tot-ans);
return 0;
}
前几题都差不多，匈牙利搜过去就好了
T5 《部落战争》hh
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);--(i))
using namespace std;
const int N=60;
int fx[5];
int fy[5];
struct Node
{
int first,second;
}L[N][N];
vector<Node> v[N][N];
int vis[N][N];
int t;
int a[N][N];
bool mt(Node tmp)
{
int x=tmp.first,y=tmp.second;
for(int i=0;i<v[x][y].size();i++)
{
int p=v[x][y][i].first;
int q=v[x][y][i].second;
if(vis[p][q]!=t)
{
vis[p][q]=t;
int ax=L[p][q].first;
int ay=L[p][q].second;
if((!ax&&!ay)||mt(L[p][q]))
{
L[p][q].first=x;
L[p][q].second=y;
return 1;
}
}
}
return 0;
}
int n,m,r,c,ans=0;
signed main(void)
{
scanf("%d%d%d%d",&m,&n,&r,&c);
fup(i,1,m)
{
fup(j,1,n)
{
char s;
cin>>s;
if(s=='.') a[i][j]=0,ans++;
else a[i][j]=1;
}
}
fx[1]=r,fy[1]=-c; fx[2]=r,fy[2]=c; fx[3]=c,fy[3]=-r; fx[4]=c,fy[4]=r;
fup(i,1,m)
{
fup(j,1,n)
{
fup(k,1,4)
{
int x=i+fx[k],y=j+fy[k];
if(x>0&&x<=m&&y>0&&y<=n&&!a[x][y])
{
Node tmp;
tmp.first=x;
tmp.second=y;
v[i][j].push_back(tmp);
}
}
}
}
int cnt=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==1)
continue;
t++;
Node tmp;
tmp.first=i,tmp.second=j;
if(mt(tmp)) cnt++;
}
}
printf("%d",t-cnt);
return 0;
}
《照搜不误》
T6 笑死了，输入问题让我WA？？？
没事，欧拉回路吗，写出脑回路很正常的
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);--(i))
using namespace std;
const int N=1e6+10;
struct Node
{
int to,nxt,from,u;
}e[N];
int head[N];
bool vis[N];
vector<int> ans;
int in[N],out[N];
int cnt;
void insert(int u,int v)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int id,n,m;
void dfs(int x)
{
for(int &j=head[x];j;j=e[j].nxt)
{
int ax=j;
if(id==1)
{
int ay=(j+1)>>1;
if(!vis[ay])
{
vis[ay]=1;
dfs(e[j].to);
if(!(ax&1)) ans.push_back(ay);
else ans.push_back(-ay);
}
}
else if(!vis[j])
{
vis[j]=1;
dfs(e[j].to);
ans.push_back(ax);
}
}
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>id>>n>>m;
fup(i,1,m)
{
int x,y;
cin>>x>>y;
out[x]++,in[y]++;
insert(x,y);
if(id==1)
insert(y,x);
}
if(id==1)
{
fup(i,1,n)
{
if((in[i]+out[i])%2)
{
puts("NO");
return 0;
}
}
}
else
{
fup(i,1,n)
{
if(in[i]!=out[i])
{
puts("NO");
return 0;
}
}
}
fup(i,1,n)
{
if(head[i])
{
dfs(i);
break;
}
}
if(ans.size()!=m)
{
puts("NO");
return 0;
}
puts("YES");
if(id==1)
{
fup(i,0,m-1)
printf("%d ",ans[i]);
return 0;
}
fdown(i,m-1,0)
printf("%d ",ans[i]);
printf("\n");
return 0;
}
T7
把首尾字母统计一下就好了
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Il inline
using namespace std;
const int N=30,M=1e5+10;
int T,n;
int incnt[N],outcnt[N];
int f[N];
char s[M>>1];
Il int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int i;
scanf("%d",&T);
while(T--)
{
memset(incnt,0,sizeof incnt);
memset(outcnt,0,sizeof outcnt);
fup(i,1,26) f[i]=i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s",s+1);
int len=strlen(s+1);
int x=s[1]-'a'+1,y=s[len]-'a'+1;
++incnt[y],++outcnt[x];
f[find(x)]=find(y);
}
int cnt=0,book=0;
for(i=1;i<=26;i++) if(abs(incnt[i]-outcnt[i])>1) { book=1; break; }
if(book)
{
puts("The door cannot be opened.");
continue;
}
for(i=1;i<=26;i++) if((incnt[i]||outcnt[i])&&find(i)==i) if((++cnt)>1) break;
if(cnt>1)
{
puts("The door cannot be opened.");
continue;
}
int left=0,right=0;
for(i=1;i<=26;i++)
{
if(incnt[i]>outcnt[i]) ++left;
else if(incnt[i]<outcnt[i]) ++right;
}
if((left!=right)||(left>1)||(right>1)) puts("The door cannot be opened.");
else puts("Ordering is possible.");
}
return 0;
}
T8
《一笔画问题？？？？？》
#include<bits/stdc++.h>
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Il inline
using namespace std;
const int N = 2e5 + 5;
int fa[N];
int in[N];
int num[N];
int ans[N];
int find (int x) {
if (fa[x] != x) fa[x] = find (fa[x]);
return fa[x];
}
int main() {
int n, m;
while (~(scanf("%d %d", &n, &m))) {
for (int i = 1; i <= n; i++) fa[i] = i;
memset (num, 0, sizeof num);
memset (ans, 0, sizeof ans);
memset (in, 0, sizeof in);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d",&x,&y);
in[x] ++;
in[y] ++;
x = find (x);
y = find (y);
if (x != y) fa[x] = y;
}
for (int i = 1; i <= n; i++) {
int x = find (i);
num[x] ++;
if (in[i] % 2 == 1) ans[x] ++;
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (num[i] <= 1) continue;
if (ans[i] == 0) res ++;
else res += ans[i] / 2;
}
printf("%d\n", res);
}
return 0;
}
写个并查集维护一下就好了，千万小心，易WA易T
T9
2-SAT的题
之前有看过
如果矛盾另外一处就连上边，tarjan缩点，染个色就完事了
#include<bits/stdc++.h>
#define N 2000
#define M 4000000
using namespace std;
int Index, instack[N], dfn[N], low[N];
int tot, color[N];
int ne, head[N];
struct Edge {
int nxt, to;
} E[M];
int stk[N], top;
int n, m;
void add(int x, int y) {
E[++ne].to = y;
E[ne].nxt = head[x];
head[x] = ne;
}
void tarjan(int x) {
stk[++top] = x;
instack[x] = 1;
dfn[x] = low[x] = ++Index;
for (int i = head[x]; i; i = E[i].nxt) {
int v = E[i].to;
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
} else if (instack[v])
low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x]) {
tot++;
do {
color[stk[top]] = tot;
instack[stk[top]] = 0;
} while (stk[top--] != x);
}
}
bool solve() {
for (int i = 0; i < 2 * n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 0; i < 2 * n; i += 2)
if (color[i] == color[i + 1])
return 0;
return 1;
}
void init() {
top = tot = Index = ne = 0;
memset(stk, 0, sizeof(stk));
memset(dfn, 0, sizeof(dfn));
memset(instack, 0, sizeof(instack));
memset(low, 0, sizeof(low));
memset(color, 0, sizeof(color));
memset(head, 0, sizeof(head));
}
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 1; i <= m; i++) {
int a1, a2, c1, c2;
scanf("%d%d%d%d", &a1, &a2, &c1, &c2);
add(2 * a1 + c1, 2 * a2 + 1 - c2);
add(2 * a2 + c2, 2 * a1 + 1 - c1);
}
if (solve())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
T10
请教今日AK的zgc大佬出山相助
#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10,M = 1e4 + 10;
int n, m;
int a[M], b[M], c[M];
struct TwoSAT
{
int n;
vector<int> G[N * 2];
bool mark[N * 2];
int S[N * 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 n) {
this->n = n;
for(int i = 0; i < n * 2; i++) G[i].clear();
memset(mark, false, sizeof(mark));
}
void calst(int x, int xval, int y, int yval) {
x = x * 2 + xval;
y = y * 2 + yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool work() {
for(int i = 0; i < n * 2; i += 2)
if(!mark[i] && !mark[i+1]) {
c = 0;
if(!dfs(i)) {
while(c > 0) mark[S[--c]] = false;
if(!dfs(i+1)) return false;
}
}
return true;
}
}Stc;
bool Do(int dep) {
Stc.init(n);
for(int i = 0; i < dep; i++) {
if(c[i] == 0) {
Stc.calst(a[i], 1, b[i], 1);
}
else if(c[i] == 1) {
Stc.calst(a[i], 1, b[i], 0);
Stc.calst(a[i], 0, b[i], 1);
}
else Stc.calst(a[i], 0, b[i], 0);
}
return Stc.work();
}
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) scanf("%d%d%d", a + i, b + i, c + i);
int left = 0, right = m;
while(left < right) {
int mid = (left + right) / 2 + 1;
if(Do(mid)) left = mid;
else right = mid - 1;
}
printf("%d\n", left);
}
return 0;
}
二分答案+2-SAT
T11
下午交了好多遍才过
其实只要2-SAT+tarjan就OK啦，中间那部分有点冗长，因为那玩意儿让我牺牲青春时光A了它
#include<bits/stdc++.h>
using namespace std;
const int N=2000000;
int f[N],a[N],b[N],d[N],stak[N],dfn[N],low[N];
bool u[N];
int j,T,n,m,cnt,tt,id,tot,i,xx,yy,x,y;
bool flag;
string s1,s2;
void add(int x,int y) {
cnt++;
a[cnt]=y;
b[cnt]=d[x];
d[x]=cnt;
}
void tarjan(int x) {
tt++;
dfn[x]=tt;
low[x]=dfn[x];
id++;
stak[id]=x;
u[x]=true;
for (int i=d[x]; i; i=b[i]) {
if (dfn[a[i]]==0) {
tarjan(a[i]);
low[x]=min(low[x],low[a[i]]);
} else if (u[a[i]]) low[x]=min(low[x],dfn[a[i]]);
}
if (low[x]==dfn[x]) {
tot++;
while (1) {
f[stak[id]]=tot;
u[stak[id]]=false;
id--;
if (stak[id+1]==x) break;
}
}
return;
}
int main() {
cin>>T;
while(T--) {
tt=0;
id=0;
tot=0;
cnt=0;
for (i=1; i<=2*n; i++) dfn[i]=0,low[i]=0,d[i]=0,u[i]=0,f[i]=0;
cin>>n>>m;
for (i=1; i<=m; i++) {
cin>>s1>>s2;
x=0;
y=0;
if (s1[0]=='m') xx=0;
else xx=1;
if (s2[0]=='m') yy=0;
else yy=1;
for (j=1; j<s1.size(); j++) x=x*10+(s1[j]-'0');
for (j=1; j<s2.size(); j++) y=y*10+(s2[j]-'0');
if ((xx==0)&(yy==0)) {
add(x+n,y);
add(y+n,x);
}
if ((xx==1)&(yy==1)) {
add(x,y+n);
add(y,x+n);
}
if ((xx==1)&(yy==0)) {
add(x,y);
add(y+n,x+n);
}
if ((xx==0)&(yy==1)) {
add(x+n,y+n);
add(y,x);
}
}
for (i=1; i<=2*n; i++)
if (dfn[i]==0) tarjan(i);
flag=true;
for (i=1; i<=n; i++)
if (f[i]==f[i+n])
flag=false;
if (flag==false) puts("BAD");
else puts("GOOD");
}
return 0;
}
e
总体吧，就那样，哪样，不太清楚，每天都不太清楚地在南外混点题来做，乱打写Code交，乱骗些分（真实感受！！！！！）
（非常真实hh