Escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2593 Accepted Submission(s): 708
Problem Description
2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.
Input
More set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000
Output
Determine whether all people can live up to these stars
If you can output YES, otherwise output NO.
If you can output YES, otherwise output NO.
Sample Input
1 1
1
1
2 2
1 0
1 0
1 1
Sample Output
YES
NO
Source
Recommend
lcy
发现可以合并点,
因为m<=10.
所以用二进制记录。
在n个点中,如果是一样的就合并。
这样最多是1024+m+2个点。
但是这题还是很坑。。。。在HDU上用G++交无论如何都是TLE的。直接读入数据输出都是TLE.
改成C++就AC了。。
1,最大流:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int VM=101000; const int EM=500010; const int INF=0x3f3f3f3f; int n,m,cnt,head[VM]; int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM]; //dep表示每个点的距离标记,gap表示距离为i的点有多少个,cur用于当前孤优化, //aug记录找到的增广路流量,path记录找到的增广路的路径。 struct Edge{ int u,v,nxt; int cap; }edge[EM]; void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].cap=0; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int SAP(int n){ int max_flow=0,u=src,v; int id,mindep; aug[src]=INF; pre[src]=-1; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=n; for(int i=0;i<=n;i++) cur[i]=head[i]; // 初始化当前弧为第一条弧 while(dep[src]<n){ int flag=0; if(u==des){ max_flow+=aug[des]; for(v=pre[des];v!=-1;v=pre[v]){ // 路径回溯更新残留网络 id=cur[v]; edge[id].cap-=aug[des]; edge[id^1].cap+=aug[des]; aug[v]-=aug[des]; // 修改可增广量,以后会用到 if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾 u=v; } } for(int i=cur[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; // 从当前弧开始查找允许弧 if(edge[i].cap>0 && dep[u]==dep[v]+1){ // 找到允许弧 flag=1; pre[v]=u; cur[u]=i; aug[v]=min(aug[u],edge[i].cap); u=v; break; } } if(!flag){ if(--gap[dep[u]]==0) /* gap优化,层次树出现断层则结束算法 */ break; mindep=n; cur[u]=head[u]; for(int i=head[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; if(edge[i].cap>0 && dep[v]<mindep){ mindep=dep[v]; cur[u]=i; // 修改标号的同时修改当前弧 } } dep[u]=mindep+1; gap[dep[u]]++; if(u!=src) // 回溯继续寻找允许弧 u=pre[u]; } } return max_flow; } int main(){ //freopen("input.txt","r",stdin); int num[1025],a[12],bit[12]; bit[0]=1; for(int i=1;i<=10;i++) bit[i]=bit[i-1]<<1; while(~scanf("%d%d",&n,&m)){ cnt=0; memset(head,-1,sizeof(head)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++){ //缩点 int tmp=0; for(int j=0;j<m;j++){ scanf("%d",&a[j]); tmp+=a[j]*bit[j]; } num[tmp]++; } src=0,des=1024+m+1; int nodenum=1024+m+2; for(int i=0;i<1024;i++){ if(num[i]==0) continue; addedge(src,i+1,num[i]); for(int j=0;j<10;j++) if(i&bit[j]) addedge(i+1,1024+j+1,INF); } int tmp; for(int i=1;i<=m;i++){ scanf("%d",&tmp); addedge(i+1024,des,tmp); } if(SAP(nodenum)==n) printf("YES\n"); else printf("NO\n"); } return 0; }
2,Hungary
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=100010; const int M=12; int map[N][M],cap[M],num[M]; //i适合在j上生存 , 星球的容量,,星球上人数 int linker[N][M],vis[M]; int n,m,flag; int in() { char ch; int a = 0; while((ch = getchar()) == ' ' || ch == '\n'); a += ch - '0'; while((ch = getchar()) != ' ' && ch != '\n') { a *= 10; a += ch - '0'; } return a; } int DFS(int u){ int v; for(v=0;v<m;v++) //枚举每个星球 if(!vis[v] && map[u][v]){ vis[v]=1; if(num[v]<cap[v]){ //i星球上人数小于容量 linker[num[v]++][v]=u; return 1; } for(int j=0;j<num[v];j++) if(DFS(linker[j][v])){ //给link[i][j]找新的星球 linker[j][v]=u; return 1; } } return 0; } void Hungary(){ //memset(linker,-1,sizeof(linker)); for(int u=0;u<n;u++){ memset(vis,0,sizeof(vis)); if(!DFS(u)){ flag=0; break; } } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) map[i][j]=in(); //此题用scanf则TLE,,哎,只能自己写输入函数了 for(int i=0;i<m;i++) scanf("%d",&cap[i]); memset(num,0,sizeof(num)); flag=1; Hungary(); if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
Hdu 1237 解题代码
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码