\u3002\u3002\u3002\u9898\u76ee\u771f\u662f\u6bd4\u8f83\u6c34\u963f\u3002\u3002\u3002\u8fde\u6211\u90fd\u5f97\u4e861000\u3002\u3002\u3002
– – – – – – – – – – – – – – – – 45384401 – – – – – – – – – – – – – – – –
– – – – – – – – – – – – – – – USACO NOV09 – – – – – – – – – – – – – – – <\/p>\n
Tom Chen \/ CHN \/ Grad: 9999 \/ Div: Gold
As an observer, YOUR RESULTS MIGHT NOT APPEAR ON THE FINAL WEB LISTINGS<\/p>\n
Below are the results of grading your submissions against the test data for
the contest.<\/p>\n
============================== SUMMARY =============================<\/p>\n
— case number —
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
cookie * * * * * * * * * *
lights * * * * * * * * * * * * * * * * *
rescue * * * * * * * * * *<\/p>\n
. = no entry t = time exceeded * = correct answer
x = wrong s = signal e = bad exit status\/…..1….\/
\u5f88\u660e\u663e\u662f\u4e00\u4e2a\u89e3\u6a21\u7ebf\u6027\u65b9\u7a0b\u7684\u6a21\u578b\u3002\u3002\u4f46\u662f\u5f88\u53ef\u80fd\u6709\u591a\u89e3\u3002\u3002
\u4f46\u5b9e\u9645\u4e0a\u53ef\u4ee5\u81ea\u7531\u53d6\u503c\u7684\u53d8\u91cf\u7684\u6570\u91cf\u4e0d\u4f1a\u8d85\u8fc7N\/2\u3002\u3002
\u6240\u4ee5\u53ea\u8981\u66b4\u529b\u679a\u4e3e\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4e2d\u9014\u8fd8\u53ef\u4ee5\u526a\u679d\u3002\u3002\u3002
Code\u3002\u3002
\/*
PROG: lights
LANG: C++
ID: Tom Chen
*\/
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=40;
int A[maxn][maxn]={0};
int N[maxn];
void init();
void solve();
int n,m;
void swap(int&x,int&y)
{int t=x;x=y;y=t;}
void init()
{
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
A[i][n+1]=A[i][i]=1,N[i]=i;
while(m–)
{
int s,t;cin>>s>>t;
A[s][t]=A[t][s]=1;
}
}
int Frees[maxn]={0},cnt=0;
bool Free[maxn]={0};
void solve()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
if(A[i][j]) break;
if(j==n+1) continue;
swap(N[i],N[j]);
for(int k=1;k<=n;k++)
swap(A[k][i],A[k][j]);
for(int j=1;j<=n;j++) if(j!=i)
if(A[j][i])
for(int k=1;k<=n+1;k++)
A[j][k]=A[j][k] xor A[i][k];
}
for(int i=1;i<=n;i++)
if(A[i][i]==0)
Frees[cnt++]=N[i],Free[N[i]]=true;
}
int ans=~0U>>1;
int C[maxn]={0};
void dfs(int pos,int now)
{
if(now>ans)
return;
if(pos==cnt)
{
for(int i=1;i<=n;i++)
if(A[i][i])
{
C[N[i]]=0;
for(int j=1;j<=n;j++)if(Free[N[j]]&&A[i][j])
C[N[i]]^=C[N[j]];
C[N[i]]^=A[i][n+1];
}
int t=count(C+1,C+n+1,1);
ans=min(ans,t);
return;
}
C[Frees[pos]]=0;dfs(pos+1,now);
C[Frees[pos]]=1;dfs(pos+1,now+1);
}
int main()
{
init();
solve();
dfs(0,0);
cout<<ans<<endl;
}
\/…..2…..\/
\u8d8a\u770b\u8d8a\u88f8\u7684\u7f51\u7edc\u6d41\u963f\u3002\u3002\u6ca1\u4ec0\u4e48\u8bdd\u8bf4\u3002\u3002\u3002
Code\u3002\u3002
\/*
PROG: cookie
LANG: C++
ID: Tom Chen
*\/
#include<iostream>
#include<math.h>
using namespace std;
const int maxn=1000+10,maxm=100+10,maxV=1500,inf=~0U>>2;
inline int Cow(int s){return s;}
inline int Group(int s){return maxn+s;}
struct edge
{
int t,c;
edge*next,*op;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxV];
void addedge(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int H[maxV]={0};
double Can[maxn]={0};
int Num[maxm]={0},N,M,vs=0,vt=maxn+maxm,V;
void init();
void solve();
int MaxFlow();
void Impossible();
void Print();
void init()
{
freopen("cookie.in","r",stdin);
freopen("cookie.out","w",stdout);
cin>>N>>M;V=N+M+2;
for(int i=1;i<=M;i++)
{
cin>>Num[i];int s;
for(int j=0;j<Num[i];j++)
{
cin>>s;
addedge(Cow(s),Group(i),1);
Can[s]+=1\/(double)Num[i];
}
}
for(int i=1;i<=N;i++)
addedge(vs,Cow(i),ceil(Can[i]));
for(int i=1;i<=M;i++)
addedge(Group(i),vt,1);
}
int aug(int no,int m)
{
if(no==vt)
return m;
int l=m;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[no]==H[i->t]+1)
{
int d=aug(i->t,min(i->c,l));
l-=d,i->c-=d,i->op->c+=d;
if(l==0||H[vs]>=V) return m-l;
}
int minh=maxV;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[i->t]<minh)
minh=H[i->t];
H[no]=minh+1;return m-l;
}
int MaxFlow()
{
int flow=0;
while(H[vs]<V)
flow+=aug(vs,inf);
return flow;
}
void solve()
{
int t=MaxFlow();
if(t<M)
Impossible();
else
Print();
}
void Impossible()
{
cout<<-1<<endl;
}
void Print()
{
for(int i=1;i<=M;i++)
{
int t=Group(i);
for(edge*i=E[t];i;i=i->next)
if(i->t!=vt&&i->c)
{
cout<<i->t<<endl;
break;
}
}
}
int main()
{
init();
solve();
}
\/….3….\/
\u8fd9\u662f\u4e00\u9053\u9648\u9898\u963f\u3002\u300206\u5e74WY\u7684\u8bba\u6587\u6709\u63d0\u5230\u8fc7\u3002\u3002\u6211\u6070\u597d\u770b\u8fc7\u3002\u3002
\u53ef\u4ee5\u53bb\u770bWY\u7684\u8bba\u6587\u963f\u3002\u3002\u6211\u5c31\u4e0d\u8bf4\u4e86\u3002\u3002\u3002
Code\u3002\u3002\u3002
\/*
PROG: rescue
LANG: C++
ID: Tom Chen
*\/
#include<iostream>
using namespace std;
int n,m;
struct point
{
int i,j,x,y,z;
void read()
{
cin>>i>>j;
x=i;
y=i-j\/2;
z=(j+1)\/2;
}
void show()
{
cout<<i<<" "<<j<<endl;
}
int operator-(const point&o) const
{return abs(x-o.x)+abs(y-o.y)+abs(z-o.z);}
};
int main()
{
freopen("rescue.in","r",stdin);
freopen("rescue.out","w",stdout);
cin>>n>>m;point now,ans;
now.read();int min=~0U>>1;
for(int i=0;i<m;i++)
{
point out;out.read();
if(now-out<min)
{
min=now-out;
ans=out;
}
}
ans.show();
cout<<min+1<<endl;
}
\/…\u603b\u7ed3…\/
1\u662f\u5f88\u57fa\u672c\u7684\u89e3\u65b9\u7a0b+\u679a\u4e3e\u3002\u3002USACO\u7684\u5206\u6790\u597d\u50cf\u662f\u679a\u4e3e\u7684\u3002\u3002\u6bd5\u7adfN\u592a\u5c0f\u4e86\u3002\u3002\u4f46\u662f\u4e0d\u4f1a\u9ad8\u65af\u6d88\u5143\u8fd8\u662f\u4e0d\u4f1a\u505a\u7684\u3002\u3002\u3002
2\u592a\u66b4\u529b\u7684\u7f51\u7edc\u6d41\u4e86\u3002\u3002\u3002
3\u6570\u5b66\u95ee\u9898\u3002\u3002WY\u7684\u8bba\u6587\u4e2d\u63d0\u8fc7\u3002\u3002\u5426\u5219\u6bd4\u8d5b\u7684\u65f6\u5019\u6211\u8fd8\u4e0d\u4e00\u5b9a\u505a\u7684\u51fa\u6765\u3002\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u3002\u3002\u3002\u9898\u76ee\u771f\u662f\u6bd4\u8f83\u6c34\u963f\u3002\u3002\u3002\u8fde\u6211\u90fd\u5f97\u4e861000\u3002\u3002\u3002– – – – – – – – – – – – – – – – 45384401 – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – USACO NOV09 – – – – – […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/17"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/17\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}