|
|
 #include <iostream>
using namespace std;
const int maxn=50001;
int father[maxn];
int rank[maxn];
void prepare(int n)
   {
 for(int i=1;i<=n;i++)
  {
father[i]=i;
rank[i]=i;
 }
 }
int find(int x)
{
if(father[x]!=x)
father[x]=find(father[x]);
return father[x];
}
void union_set(int x,int y)
{
int fx,fy;
fx=find(x);
fy=find(y);
if(rank[fx]>rank[fy])
father[fy]=fx;
else if(rank[fx]<rank[fy])
father[fx]=fy;
else
{
father[fy]=fx;
rank[fx]++;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin) ;
#endif
int n,m,i;
int casen=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
casen++;
if(n==0&&m==0) break;
prepare(n);
int sum=0;
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
union_set(x,y);
}
for(i=1;i<=n;i++)
if(father[i]==i) sum++;
printf("Case %d: %d\n",casen,sum);
}
return 0;
}
#include <iostream>
using namespace std;
#define init(I) memset(I,0,sizeof(I))
const int maxn=101;
struct edge
{
int data;
edge *next;
};
edge *g1[maxn],*g2[maxn],*g[maxn];
int vis[maxn],path[maxn],scc[maxn],mark[maxn][maxn];
int out[maxn],in[maxn];
int n,m,cnt;
void add(edge* t[],int s,int e){
edge *p;
p=new edge;
p->data=e;
p->next=t[s];
t[s]=p;
}
void dfs1(int s){
vis[s]=1;
edge *p;
for(p=g1[s];p;p=p->next)
if(!vis[p->data])
dfs1(p->data);
path[0]++;
path[path[0]]=s;
}
void dfs2(int s){
vis[s]=1;
scc[s]=scc[0];
edge *p;
for(p=g2[s];p;p=p->next)
if(!vis[p->data])
dfs2(p->data);
}
void shrink(){
int s,e,k;
init(mark);
edge *p;
for(k=1;k<=n;k++)
for(p=g1[k],s=scc[k];p;p=p->next)
{
e=scc[p->data];
if(s!=e&&!mark[s][e])
{
mark[s][e]=1;
add(g,s,e);
}
}
}
void kosaraju()
{
int i;
path[0]=scc[0]=0;
init(vis);
for(i=1;i<=n;i++)
if(!vis[i])
dfs1(i);
init(vis);
for(i=n;i>=1;i--)
{
if(!vis[path[i]])
{
scc[0]++;
dfs2(path[i]);
}
}
}
int main()
{
int to,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
g1[i]=g2[i]=g[i]=NULL;
for(i=1;i<=n;i++)
{
while(scanf("%d",&to)&&to)
{
add(g1,i,to);
add(g2,to,i);
}
}
kosaraju();
shrink();
init(out);
init(in);
int cnt=scc[0];
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)
if(mark[i][j])
{
out[i]++;
in[j]++;
}
if(cnt==1)
{
printf("1\n0\n");
return 0;
}
int t1=0,t2=0;
for(i=1;i<=cnt;i++)
{
if(in[i]==0) t1++;
if(out[i]==0) t2++;
}
printf("%d\n",t1);
printf("%d\n",t1>t2?t1:t2);
return 0;
}
#include <iostream>
using namespace std;
const int maxn=1001;
int c[maxn][maxn];
int T,n,m;
int lowBit(int i){return i&(-i);}
void add(int i,int j,int val)
{
while(i>0)
{
int temp=j;
while(temp>0)
{
c[i][temp]+=val;
temp-=lowBit(temp);
}
i-=lowBit(i);
}
}
int sum(int i,int j)
{
int s=0;
while(i<=n)
{
int temp=j;
while(temp<=n)
{
s+=c[i][temp];
temp+=lowBit(temp);
}
i+=lowBit(i);
}
return s%2;
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
char s;
scanf("%s",&s);
if(s=='C')
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add(x2,y2,1);
add(x1-1,y2,-1);
add(x2,y1-1,-1);
add(x1-1,y1-1,1);
}
if(s=='Q')
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",sum(x,y));
}
}
printf("\n");
}
return 0;
}
#include <iostream>
using namespace std;
#define maxn 401
int g[maxn][maxn];//容量
int f[maxn][maxn];//流量
int r[maxn][maxn];//残量
int Edmonds_Karp(int g[][maxn],int s,int t,int f[][maxn])
{
int i,j,k,c,head,tail,flow=0 ;
int prev[maxn],visit[maxn],q[maxn];
for(i=s;i<=t;i++)for(j=s;j<=t;j++)
{
f[i][j]=0 ;
r[i][j]=g[i][j];
}
while(1)
{
head=tail=0 ;
memset(visit,0,sizeof(visit));
q[tail++]=s ;
prev[s]=-1 ;
visit[s]=1 ;
while(head<tail)
{
k=q[head++];
for(i=s;i<=t;i++) //注意修改
if(!visit[i]&&r[k][i]>0)
{
visit[i]=1 ;
prev[i]=k ;
if(i==t)goto next ;
q[tail++]=i ;
}
}
next :
if(!visit[t])break ;
for(c=INT_MAX,j=t;j!=s;j=i)
{
i=prev[j];
if(c>r[i][j])c=r[i][j];
}
for(j=t;j!=s;j=i)
{
i=prev[j];
f[i][j]+=c ;
f[j][i]=-f[i][j];
r[i][j]=g[i][j]-f[i][j];
r[j][i]=g[j][i]-f[j][i];
}
flow+=c ;
}
return flow ;
}
int main()
{
int i,j;
int s,t;
int F,N,D;
scanf("%d%d%d",&N,&F,&D);
s=0;
t=F+N+N+D+1;
for(i=1;i<=N;i++)
{
int m,n,k;
scanf("%d%d",&m,&n);
for(j=1;j<=m;j++)//Food->Cow
{
scanf("%d",&k);
g[k][i+F]=1;
}
for(j=1;j<=n;j++)//Cow->Drink
{
scanf("%d",&k);
g[i+F+N][k+F+N+N]=1;
}
}
for(i=1;i<=F;i++)//Sourse->Food
g[s][i]=1;
for(i=1;i<=N;i++)//Cow->Cow
g[F+i][F+N+i]=1;
for(i=1;i<=D;i++)//Drink->Terminal
g[i+F+N+N][t]=1;
printf("%d\n",Edmonds_Karp(g,s,t,f));
return 0;
}
#include <iostream>
using namespace std;
#define N 105
int Edmonds_Karp(int g[][N],int n,int s,int t,int f[][N])
{
int i,j,k,c,head,tail,flow=0 ;
int r[N][N];
int prev[N],visit[N],q[N];
for(i=s;i<=t;i++)for(j=s;j<=t;j++)
{
f[i][j]=0 ;
r[i][j]=g[i][j];
}
while(1)
{
head=tail=0 ;
memset(visit,0,sizeof(visit));
q[tail++]=s ;
prev[s]=-1 ;
visit[s]=1 ;
while(head<tail)
{
k=q[head++];
for(i=s;i<=t;i++) //注意修改
if(!visit[i]&&r[k][i]>0)
{
visit[i]=1 ;
prev[i]=k ;
if(i==t)goto next ;
q[tail++]=i ;
}
}
next :
if(!visit[t])break ;
for(c=INT_MAX,j=t;j!=s;j=i)
{
i=prev[j];
if(c>r[i][j])c=r[i][j];
}
for(j=t;j!=s;j=i)
{
i=prev[j];
f[i][j]+=c ;
f[j][i]=-f[i][j];
r[i][j]=g[i][j]-f[i][j];
r[j][i]=g[j][i]-f[j][i];
}
flow+=c ;
}
return flow ;
}
int g[N][N];
int f[N][N];
int main()
{
int i,j,k,x;
int n,m;
int s,t;
scanf("%d%d",&m,&n);
int num[1005];
int ff[1005];
for(i=1;i<=m;i++)
{
scanf("%d",&num[i]);
ff[i]=0;
}
for(j=1;j<=n;j++)
{
int temp;
scanf("%d",&temp);
for(k=0;k<temp;k++)
{
scanf("%d",&x);
if(ff[x]==0)
{
g[0][j]+=num[x];
ff[x]=j;
}
else {g[ff[x]][j]=INT_MAX;ff[x]=j;}
}
scanf("%d",&temp);
g[j][n+1]=temp;
}
s=0;t=n+1;
printf("%d\n",Edmonds_Karp(g,n,s,t,f));
return 0;
}
#include <iostream>
using namespace std;
const int maxn=1025;
const int maxm=100000;
struct gtype
{
int x,y,next;
};
gtype g[maxm];
int first[maxn];
int link[maxn];
bool used[maxn];
int f2[11]={1,2,4,8,16,32,64,128,256,512,1024};
bool in[1025];
int cheese[1025];
int n,m,tot;
int i,j,all;
void add(int x,int y)
{
tot++;
g[tot].x=x;g[tot].y=y;
g[tot].next=first[x];
first[x]=tot;
}
bool find(int s)
{
int temp=first[s];
while(temp!=-1)
{
int e=g[temp].y;
if(!used[e])
{
used[e]=true;
if(link[e]==0||find(link[e]))
{
link[e]=s;
return 1;
}
}
temp=g[temp].next;
}
return 0;
}
int match()
{
int sum=0;
for(i=0;i<all;i++)
{
memset(used,0,sizeof(used));
sum+=find(i);
}
return sum;
}
bool check(int a,int b)
{
int t=cheese[a]^cheese[b];
return t&&(t&(t-1))==0;
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0) break;
memset(first,-1,sizeof(first));
memset(link,0,sizeof(link));
char s;
for(i=0;i<m;i++)
{
int flag=-1;
int t=0;
for(j=0;j<n;j++)
{
cin>>s;
if(s=='*')
{
flag=j;
continue;
}
t+=(s-'0')*f2[j];
}
in[t]=true;
if(flag!=-1)
in[t+f2[flag]]=true;
}
all=0;
for(i=0;i<(1<<n);i++)
if(in[i])
cheese[all++]=i;
for(i=0;i<all;i++)
for(j=0;j<all;j++)
{
if(i==j) continue;
if(check(i,j))
add(i,j);
}
int ans=all-match()/2;
cout<<ans<<endl;
}
return 0;
}
#include <iostream>
#include <set>
#include <string>
#include <queue>
using namespace std;
struct state{
long a;
long b;
long c;
state(long i,long j,long k):a(i),b(j),c(k)
{}
};
struct peg{
state s;
int c;
peg(state z,int cc):s(z),c(cc)
{}
};
bool operator==(const state& a,const state& b){
return a.a==b.a&&a.b==b.b&&a.c==b.c;
}
bool operator<(const state& a,const state& b){
if(a.a!=b.a) return a.a<b.a;
if(a.b!=b.b) return a.b<b.b;
return a.c<b.c;
}
set<state> vis;
long conv(const string& a){
long r=0;
for(int i=0;i<a.size();i++){
r=r*4+(a[i]-'A'+1);
}
return r;
}
class HanoiTower{
public:
int moves(string pegA,string pegB,string pegC){
int r=0;
queue<peg> q;
q.push( peg( state( conv(pegA),conv(pegB),conv(pegC) ), 0 ) );
int numA=0,numB=0,numC=0;
string big=pegA+pegB+pegC;
for(int i=0;i<big.size();i++){
if(big[i]=='A') numA++;
else if(big[i]=='B') numB++;
else numC++;
}
string tA=string(numA,'A'),tB=string(numB,'B'),tC=string(numC,'C');
state target=state(conv(tA),conv(tB),conv(tC));
while(!q.empty()){
peg z=q.front();q.pop();
if(z.s==target) return z.c;
if(vis.count(z.s)!=0) continue;
vis.insert(z.s);
long aa=z.s.a;
long bb=z.s.b;
long cc=z.s.c;
if(aa>0){
int m=aa%4;
q.push( peg( state((aa-m)/4,bb*4+m,cc),z.c+1));
q.push( peg( state((aa-m)/4,bb,cc*4+m),z.c+1));
}
if(bb>0){
int m=bb%4;
q.push( peg( state(aa*4+m,(bb-m)/4,cc),z.c+1));
q.push( peg( state(aa,(bb-m)/4,cc*4+m),z.c+1));
}
if(cc>0){
int m=cc%4;
q.push( peg( state(aa,bb*4+m,(cc-m)/4),z.c+1) );
q.push( peg( state(aa*4+m,bb,(cc-m)/4),z.c+1) );
}
}
return r;
}
};
|